Undecidability of regular winning-position languages for strongly terminating games
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Eric Duchêne, Victor Marsault, Aline Parreau and Michel Rigo, “Taking-and-merging games as rewrite games”, arXiv:1902.07011 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.