Undecidability of regular winning-position languages for strongly terminating games
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.