Undecidability of regular winning-position languages for strongly terminating games

At least 6 years old · documented by

A strongly terminating game is a game G\mathcal{G} in which every play terminates. The winning positions of G\mathcal{G} are the positions from which the winning player can force a win; these positions form a language over the game's position alphabet.

The conjecture. Given a strongly terminating game G\mathcal{G}, it is undecidable whether the winning positions of G\mathcal{G} form a regular language.

The paper presents this as an open problem in the context of taking-and-merging games. The preceding results establish undecidability for related restricted questions, but the supplied text does not give a proof of this stronger regularity problem.

References

Primary source

Eric Duchêne, Victor Marsault, Aline Parreau and Michel Rigo, “Taking-and-merging games as rewrite games”, arXiv:1902.07011 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.