Undecidability of regular winning-position languages for strongly terminating games
A strongly terminating game is a game in which every play terminates. The winning positions of 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 , it is undecidable whether the winning positions of 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
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.