# Shortest string in the intersection of regular languages

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 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 on the question if it tempts anyone.

• 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 Oct 22 '18 at 16:41
• 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 Oct 22 '18 at 18:01
• @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 Oct 23 '18 at 14:03
• @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 Oct 23 '18 at 16:06
• 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 Oct 24 '18 at 14:00