Document Open Access Logo

Minkowski Games

Authors Stéphane Le Roux, Arno Pauly, Jean-François Raskin

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.50.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Stéphane Le Roux
Arno Pauly
Jean-François Raskin

Cite As Get BibTex

Stéphane Le Roux, Arno Pauly, and Jean-François Raskin. Minkowski Games. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.50

Abstract

We introduce and study Minkowski games. In these games, two players take turns to choose positions in R^d based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded (while the other wants to escape to infinity), and safety games, where one player wants to stay within a given set (while the other wants to leave it).

We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable.

Subject Classification

Keywords
  • Control in R^d
  • determinacy
  • polytopic/arbitrary
  • coNP-complete
  • undecidable

Metrics

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

References

  1. Rajeev Alur, Vojtech Forejt, Salar Moarref, and Ashutosh Trivedi. Safe schedulability of bounded-rate multi-mode systems. In Proceedings of the 16th international conference on Hybrid systems: computation and control, HSCC 2013, April 8-11, 2013, Philadelphia, PA, USA, pages 243-252. ACM, 2013. Google Scholar
  2. Rajeev Alur, Ashutosh Trivedi, and Dominik Wojtczak. Optimal scheduling for constant-rate multi-mode systems. In Hybrid Systems: Computation and Control (part of CPS Week 2012), HSCC'12, Beijing, China, April 17-19, 2012, pages 75-84. ACM, 2012. Google Scholar
  3. Michael Ben-Or, Dexter Kozen, and John Reif. The complexity of elementary algebra and geometry. Journal of Computer and Systems Sciences, 32(2):251-264, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90029-2.
  4. Bernard Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry, 10:377-409, 1993. URL: http://dx.doi.org/10.1007/BF02573985.
  5. James H. Davenport and Joos Heintz. Real quantifier elimination is doubly exponential. Journal of Symbolic Computation, 5(1):29-35, 1988. URL: http://dx.doi.org/10.1016/S0747-7171(88)80004-X.
  6. Rod Downey and Michael Fellows. Parameterized Complexity. Springer, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0515-9.
  7. Laurent Doyen and Alexander Rabinovich. Robot games. Research Report LSV-13-02, Laboratoire Spécification et Vérification, ENS Cachan, France, 2013. URL: http://www.lsv.ens-cachan.fr/Publis/RAPPORTS_LSV/PDF/rr-lsv-2013-02.pdf.
  8. Thomas A. Henzinger, Benjamin Horowitz, and Rupak Majumdar. Rectangular hybrid games. In CONCUR'99: Concurrency Theory, 10th International Conference, Eindhoven, The Netherlands, August 24-27, 1999, Proceedings, volume 1664 of Lecture Notes in Computer Science, pages 320-335. Springer, 1999. Google Scholar
  9. Thomas A. Henzinger and Peter W. Kopke. Discrete-time control for rectangular hybrid automata. In Automata, Languages and Programming, 24th International Colloquium, ICALP'97, Bologna, Italy, 7-11 July 1997, Proceedings, volume 1256 of Lecture Notes in Computer Science, pages 582-593. Springer, 1997. Google Scholar
  10. Stéphane Le Roux and Arno Pauly. Finite choice, convex choice and finding roots. Logical Methods in Computer Science, 2015. URL: http://dx.doi.org/10.2168/LMCS-11(4:6)2015.
  11. Oded Maler, Amir Pnueli, and Joseph Sifakis. On the synthesis of discrete controllers for timed systems (an extended abstract). In STACS, pages 229-242, 1995. Google Scholar
  12. Marvin L. Minsky. Recursive unsolvability of Post’s problem of "tag" and other topics in theory of Turing machines. Annals of Mathematics, 74(3):437-455, 1961. Google Scholar
  13. Reino Niskanen, Igor Potapov, and Julien Reichert. Undecidability of Two-dimensional Robot Games. In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors, 41st Int. Sym. on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of LIPIcs, pages 73:1-73:13. Schloss Dagstuhl, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.73.
  14. Arno Pauly. On the topological aspects of the theory of represented spaces. Computability, 5(2):159-180, 2016. URL: http://dx.doi.org/10.3233/COM-150049.
  15. Amir Pnueli and Roni Rosner. On the synthesis of a reactive module. In Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, Austin, Texas, USA, January 11-13, 1989, pages 179-190. ACM Press, 1989. Google Scholar
  16. Stéphane Le Roux, Arno Pauly, and Jean-François Raskin. Minkowski games. CoRR, abs/1609.07048, 2016. URL: http://arxiv.org/abs/1609.07048.
  17. Klaus Weihrauch. Computable Analysis. Springer-Verlag, 2000. Google Scholar
  18. Martin Ziegler. Computable operators on regular sets. Mathematical Logic Quarterly, 50:392-404, 2004. Google Scholar
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