License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.73
URN: urn:nbn:de:0030-drops-64839
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6483/
Go to the corresponding LIPIcs Volume Portal

Niskanen, Reino ; Potapov, Igor ; Reichert, Julien

Undecidability of Two-dimensional Robot Games

pdf-format:
LIPIcs-MFCS-2016-73.pdf (0.5 MB)

Abstract

Robot game is a two-player vector addition game played on the integer lattice 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.

BibTeX - Entry

@InProceedings{niskanen_et_al:LIPIcs:2016:6483,
  author =	{Reino Niskanen and Igor Potapov and Julien Reichert},
  title =	{{Undecidability of Two-dimensional Robot Games}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{73:1--73:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6483},
  URN =		{urn:nbn:de:0030-drops-64839},
  doi =		{10.4230/LIPIcs.MFCS.2016.73},
  annote =	{Keywords: reachability games, vector addition game, decidability, winning strategy}
}

Keywords: reachability games, vector addition game, decidability, winning strategy
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI