Document Open Access Logo

Undecidability of Two-dimensional Robot Games

Authors Reino Niskanen, Igor Potapov, Julien Reichert

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.73.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Reino Niskanen
Igor Potapov
Julien Reichert

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.MFCS.2016.73

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.

Subject Classification

Keywords
  • reachability games
  • vector addition game
  • decidability
  • winning strategy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Parosh Aziz Abdulla, Ahmed Bouajjani, and Julien d'Orso. Deciding monotonic games. In Proceedings of CSL 2003, volume 2803 of LNCS, pages 1-14, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45220-1_1.
  2. Parosh Aziz Abdulla, Ahmed Bouajjani, and Julien d'Orso. Monotonic and downward closed games. J. Log. Comput., 18(1):153-169, 2008. URL: http://dx.doi.org/10.1093/logcom/exm062.
  3. Parosh Aziz Abdulla, Richard Mayr, Arnaud Sangnier, and Jeremy Sproston. Solving parity games on integer vectors. In Proceedings of CONCUR 2013, volume 8052 of LNCS, pages 106-120, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40184-8_9.
  4. Arjun Arul and Julien Reichert. The complexity of robot games on the integer line. In Proceedings of QAPL 2013, volume 117 of EPTCS, pages 132-148, 2013. URL: http://dx.doi.org/10.4204/EPTCS.117.9.
  5. Tomás Brázdil, Václav Brozek, and Kousha Etessami. One-counter stochastic games. In In proceedings of FSTTCS 2010, volume 8 of LIPIcs, pages 108-119, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.108.
  6. Tomáš Brázdil, Petr Jančar, and Antonín Kučera. Reachability games on extended vector addition systems with states. In Proceedings of ICALP 2010, volume 6199 of LNCS, pages 478-489, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14162-1_40.
  7. Jakub Chaloupka. Z-reachability problem for games on 2-dimensional vector addition systems with states is in P. Fundam. Inform., 123(1):15-42, 2013. URL: http://dx.doi.org/10.3233/FI-2013-798.
  8. Krishnendu Chatterjee and Laurent Doyen. Energy parity games. Theor. Comput. Sci., 458:49-60, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.07.038.
  9. Laurent Doyen and Alexander Rabinovich. Robot games. Personal website, 2011. Technical Report LSV-13-02, LSV, ENS Cachan, 2013. URL: http://www.lsv.ens-cachan.fr/Publis/RAPPORTS%5FLSV/PDF/rr-lsv-2013-02.pdf.
  10. Uli Fahrenberg, Line Juhl, Kim G. Larsen, and Jirí Srba. Energy games in multiweighted automata. In Proceedings of ICTAC 2011, volume 6916 of LNCS, pages 95-115, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23283-1_9.
  11. Vesa Halava, Tero Harju, Reino Niskanen, and Igor Potapov. Weighted automata on infinite words in the context of Attacker-Defender games. In Proceedings of CiE 2015, volume 9136 of LNCS, pages 206-215, 2015. URL: http://dx.doi.org/10.1007/978-3-319-20028-6_21.
  12. Vesa Halava, Reino Niskanen, and Igor Potapov. On robot games of degree two. In Proceedings of LATA 2015, volume 8977 of LNCS, pages 224-236, 2015. URL: http://dx.doi.org/10.1007/978-3-319-15579-1_17.
  13. Paul Hunter. Reachability in succinct one-counter games. In Proceedings of RP 2015, volume 9328 of LNCS, pages 37-49, 2015. URL: http://dx.doi.org/10.1007/978-3-319-24537-9_5.
  14. Ivan Korec. Small universal register machines. Theor. Comput. Sci., 168(2):267-301, 1996. URL: http://dx.doi.org/10.1016/S0304-3975(96)00080-1.
  15. Donald A. Martin. Borel determinacy. Annals of Mathematics, 102(2):363-371, 1975. URL: http://dx.doi.org/10.2307/1971035.
  16. Marvin L Minsky. Computation: finite and infinite machines. Prentice-Hall, Inc., 1967. Google Scholar
  17. Reino Niskanen, Igor Potapov, and Julien Reichert. Undecidability of two-dimensional robot games. CoRR, abs/1604.08779, 2016. URL: http://arxiv.org/abs/1604.08779.
  18. Julien Reichert. Reachability Games with Counters: Decidability and Algorithms. Doctoral thesis, Laboratoire Spécification et Vérification, ENS Cachan, France, 2015. Google Scholar
  19. Julien Reichert. On the complexity of counter reachability games. Fundam. Inform., 143(3-4):415-436, 2016. URL: http://dx.doi.org/10.3233/FI-2016-1320.
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 About DROPS Imprint Privacy Contact