Undecidability of regular winning-position languages for strongly terminating games

From papers

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.

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

No solutions have been posted yet.