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 supports Monica 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 supports Monica Oct 24 '18 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.