9
$\begingroup$

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 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Chao Xu Oct 22 '18 at 16:41
  • 1
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Oct 22 '18 at 18:01
  • 1
    $\begingroup$ @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 $\endgroup$ – ghosts_in_the_code Oct 23 '18 at 14:03
  • 1
    $\begingroup$ @MichaelWehar That seems helpful. I didn't know about DFA minimisation. I'll see if I can read up and figure anything out. $\endgroup$ – ghosts_in_the_code Oct 23 '18 at 16:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Oct 24 '18 at 14:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.