<p>Inspired by <a href="https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string">https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string</a></p>

<p>Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ending states) that uses a 4-letter alphabet.</p>

<p>Each maze hence directly corresponds to a regular language. The intersection of all the regular languages is also a regular language with each string in it representing a valid "universal exit string". And we now have to find the shortest such string.</p>

<p>So is there any algorithm, construction, etc that can help us find the shortest such string? </p>

<p>I found this <a href="https://uwspace.uwaterloo.ca/handle/10012/5162" rel="noreferrer">paper</a> by Thomas Ang on googling but couldn't find anything in it I could use in the problem (I could be mistaken).</p>

<p>I'm just making this post to find out if any already existing results/approaches in theoretical CS can be used to solve the problem.</p>

<p>Thanks</p>

<p>P.S. There's an <a href="https://codegolf.meta.stackexchange.com/a/10392/40929">unofficial bounty</a> on the question if it tempts anyone.</p>

CC BY-SA 4.0
2018-10-22T16:07:16.190Z
There is some work on intersecting many regular languages. I have no idea if it is practical though: see here https://link.springer.com/chapter/10.1007/978-3-642-30642-6_4 if you don't have access, don't use scihub. In particular don't go to wikipedia to check for the last valid scihub address. It is against the law even though nobody will notice and editors are evils.
C.P.
CC BY-SA 4.0
2018-10-22T16:41:59.890Z
There are examples where the length of the string is exponential to the number of input DFAs. I guess one might ask if there is a polynomial time algorithm parametrized by length.
Chao Xu
CC BY-SA 4.0
2018-10-22T18:01:11.817Z
Note also that the number of DFAs here is already exponential, so you only get a *doubly exponential* bound on the length of the string in this way. As far as I can see, this is ridiculously suboptimal (by properties of random walks, there is a “universal exit string” of *polynomial* length, and even a randomly chosen string of such length is a u.e.s. with high probability).
Emil Jeřábek
CC BY-SA 4.0
2018-10-23T13:54:37.267Z
Suppose that you have $k$ regular languages where each regular language is recognized by some DFA with at most $n$ states.  Then, in the worst case, the intersection of the $k$ regular language cannot be recognized by a DFA with fewer than $n^{\Theta(k)}$ states.
Michael Wehar
CC BY-SA 4.0
2018-10-23T13:57:13.270Z
A lot can be said about the state complexity of the intersection of regular languages and my comments were just brief statements that could be refined.  I'm quite interested in this topic and am always happy to chat about this.  :)
Michael Wehar
CC BY-SA 4.0
2018-10-23T14:03:22.523Z
@MichaelWehar and others, thanks for replying. I guess then it's better to not approach the problem from a theoretical CS way, and find some sort of random or approximation approach rather than an algorithm that can find a provably optimal exit string. Is that what I should infer? Also I'm just a student who's interested in all this so I won't be able to provide any value by chatting. Thanks anyways
ghosts_in_the_code
CC BY-SA 4.0
2018-10-23T15:58:57.223Z
@ghosts_in_the_code One insight that might be helpful is that the length of the shortest string is at most the state complexity of the intersection.
Michael Wehar
CC BY-SA 4.0
2018-10-23T16:00:04.463Z
You could strategically compute a DFA that recognizes the intersection language by taking products and running DFA minimization.
Michael Wehar
CC BY-SA 4.0
2018-10-23T16:06:23.267Z
@MichaelWehar That seems helpful. I didn't know about DFA minimisation. I'll see if I can read up and figure anything out.
ghosts_in_the_code
CC BY-SA 4.0
2018-10-23T16:13:41.333Z
@MichaelWehar For DFA minimisation, could I just use the existing algorithms or is some thinking required here also? And (not relevant but) is there any library/api/graphical interface/etc that makes coding for dfas easy?
ghosts_in_the_code
CC BY-SA 4.0
2018-10-23T16:18:33.483Z
@MichaelWehar Okay I found this: https://pypi.org/project/automata-lib/ Would you recommend it or something else?
ghosts_in_the_code
CC BY-SA 4.0
2018-10-24T09:42:41.303Z
@ghosts_in_the_code This library looks pretty neat!  Looking at the document, it supports minimization, but I'm not sure if it supports products.
Michael Wehar
CC BY-SA 4.0
2018-10-24T09:49:28.587Z
I've never used it, but this Java library seems to support minimization and product operations like intersection.  Link: http://www.brics.dk/automaton/
Michael Wehar
CC BY-SA 4.0
2018-10-24T10:07:30.623Z
@MichaelWehar Isn't there a list on SE or elsewhere of all available tools for automata and Turing machine related coding? I don't know Java actually.
ghosts_in_the_code
CC BY-SA 4.0
2018-10-24T14:00:40.527Z
Concerning “it's better to not approach the problem from a theoretical CS way”: I wouldn’t be so sure about this; I’d rather say that other TCS approaches may be more fruitful than DFA minimization. In particular, there is considerable literature on *universal traversal sequences* on graphs, of which your problem is a special case.
Emil Jeřábek
CC BY-SA 4.0
2018-10-24T20:52:13.100Z
@ghosts_in_the_code I'm not sure, but I'm really glad that you asked this in a new question.  Link to new question: https://cstheory.stackexchange.com/questions/41786/libraries-for-programming-automata-and-turing-machines
Michael Wehar
<optimization><automata-theory><regular-language><dfa><regular-expressions>
Shortest string in the intersection of regular languages
ghosts_in_the_code
# Shortest string in the intersection of regular languages

(Asked by: username_0 on 2018-10-22)

Inspired by <https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string>

Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ending states) that uses a 4-letter alphabet.

Each maze hence directly corresponds to a regular language. The intersection of all the regular languages is also a regular language with each string in it representing a valid "universal exit string". And we now have to find the shortest such string.

So is there any algorithm, construction, etc that can help us find the shortest such string?

I found this [paper](https://uwspace.uwaterloo.ca/handle/10012/5162) by Thomas Ang on googling but couldn't find anything in it I could use in the problem (I could be mistaken).

I'm just making this post to find out if any already existing results/approaches in theoretical CS can be used to solve the problem.

Thanks

P.S. There's an [unofficial bounty](https://codegolf.meta.stackexchange.com/a/10392/40929) on the question if it tempts anyone.

**Tags:** optimization, automata-theory, regular-language, dfa, regular-expressions
> **Comments:**
> **username_1**: There is some work on intersecting many regular languages. I have no idea if it is practical though: see here https://link.springer.com/chapter/10.1007/978-3-642-30642-6_4 if you don't have access, don't use scihub. In particular don't go to wikipedia to check for the last valid scihub address. It is against the law even though nobody will notice and editors are evils.  
> **username_2**: There are examples where the length of the string is exponential to the number of input DFAs. I guess one might ask if there is a polynomial time algorithm parametrized by length.  
> **username_3**: Note also that the number of DFAs here is already exponential, so you only get a *doubly exponential* bound on the length of the string in this way. As far as I can see, this is ridiculously suboptimal (by properties of random walks, there is a “universal exit string” of *polynomial* length, and even a randomly chosen string of such length is a u.e.s. with high probability).  
> **username_4**: Suppose that you have $k$ regular languages where each regular language is recognized by some DFA with at most $n$ states.  Then, in the worst case, the intersection of the $k$ regular language cannot be recognized by a DFA with fewer than $n^{\Theta(k)}$ states.  
> **username_4**: A lot can be said about the state complexity of the intersection of regular languages and my comments were just brief statements that could be refined.  I'm quite interested in this topic and am always happy to chat about this.  :)  
> **username_0**: @MichaelWehar and others, thanks for replying. I guess then it's better to not approach the problem from a theoretical CS way, and find some sort of random or approximation approach rather than an algorithm that can find a provably optimal exit string. Is that what I should infer? Also I'm just a student who's interested in all this so I won't be able to provide any value by chatting. Thanks anyways  
> **username_4**: @ghosts_in_the_code One insight that might be helpful is that the length of the shortest string is at most the state complexity of the intersection.  
> **username_4**: You could strategically compute a DFA that recognizes the intersection language by taking products and running DFA minimization.  
> **username_0**: @MichaelWehar That seems helpful. I didn't know about DFA minimisation. I'll see if I can read up and figure anything out.  
> **username_0**: @MichaelWehar For DFA minimisation, could I just use the existing algorithms or is some thinking required here also? And (not relevant but) is there any library/api/graphical interface/etc that makes coding for dfas easy?  
> **username_0**: @MichaelWehar Okay I found this: https://pypi.org/project/automata-lib/ Would you recommend it or something else?  
> **username_4**: @ghosts_in_the_code This library looks pretty neat!  Looking at the document, it supports minimization, but I'm not sure if it supports products.  
> **username_4**: I've never used it, but this Java library seems to support minimization and product operations like intersection.  Link: http://www.brics.dk/automaton/  
> **username_0**: @MichaelWehar Isn't there a list on SE or elsewhere of all available tools for automata and Turing machine related coding? I don't know Java actually.  
> **username_3**: Concerning “it's better to not approach the problem from a theoretical CS way”: I wouldn’t be so sure about this; I’d rather say that other TCS approaches may be more fruitful than DFA minimization. In particular, there is considerable literature on *universal traversal sequences* on graphs, of which your problem is a special case.  
> **username_4**: @ghosts_in_the_code I'm not sure, but I'm really glad that you asked this in a new question.  Link to new question: https://cstheory.stackexchange.com/questions/41786/libraries-for-programming-automata-and-turing-machines  

---

## 0 answers

