Undecidability of two-dimensional robot games

DOI10.4230/LIPICS.MFCS.2016.73MaRDI QIDQ4608636zbMATH OpenOpenAlexFDO

Authors Reino Niskanen, Igor Potapov, J. Reichert

Publication date 21 March 2018

Full work available at URL https://arxiv.org/abs/1604.08779

zbMATH Keywords

decidabilityreachability gamesvector addition gamewinning strategy

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) 2-person games (91A05) Games involving graphs (91A43)

Abstract: Robot game is a two-player vector addition game played on the integer lattice $mathbb{Z}^n$. Both players have sets of vectors and in each turn the vector chosen by a player is added to the current configuration vector of the game. One of the players, called Eve, tries to play the game from the initial configuration to the origin while the other player, Adam, tries to avoid the origin. The problem is to decide whether or not Eve has a winning strategy. In this paper we prove undecidability of the robot game in dimension two answering the question formulated by Doyen and Rabinovich in 2011 and closing the gap between undecidable and decidable cases.

Recommendations

• On decidability and complexity of low-dimensional robot games
• On robot games of degree two
• Robot games with states in dimension one
• The complexity of robot games on the integer line
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P

Cited in

(8)

• Robot games with states in dimension one
• On decidability and complexity of low-dimensional robot games
• Weighted automata on infinite words in the context of attacker-defender games
• Hyperplane separation technique for multidimensional mean-payoff games
• On robot games of degree two
• Bounding Average-Energy Games
• The complexity of robot games on the integer line
• History-deterministic vector addition systems

This page was built for publication: Undecidability of two-dimensional robot games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608636)