1 Search Results for "Reichert, Julien"

Document
DOI: 10.4230/LIPIcs.MFCS.2016.73
Undecidability of Two-dimensional Robot Games

Authors: Reino Niskanen, Igor Potapov, and Julien Reichert

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

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.
Cite as

Reino Niskanen, Igor Potapov, and Julien Reichert. Undecidability of Two-dimensional Robot Games. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 73:1-73:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{niskanen_et_al:LIPIcs.MFCS.2016.73,
  author =	{Niskanen, Reino and Potapov, Igor and Reichert, Julien},
  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 =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.73},
  URN =		{urn:nbn:de:0030-drops-64839},
  doi =		{10.4230/LIPIcs.MFCS.2016.73},
  annote =	{Keywords: reachability games, vector addition game, decidability, winning strategy}
}
  • Refine by Author
  • 1 Niskanen, Reino
  • 1 Potapov, Igor
  • 1 Reichert, Julien

  • Refine by Classification

  • Refine by Keyword
  • 1 decidability
  • 1 reachability games
  • 1 vector addition game
  • 1 winning strategy

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact