Stéphane Le Roux
Skip Abstract Section
Abstract
We introduce and study Minkowski games. These are two-player games, where the players take turns to choose positions in R<sup<d</sup< based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety games, where one player wants to stay within a prescribed 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.
- Rajeev Alur, Vojtech Forejt, Salar Moarref, and Ashutosh Trivedi. 2013. Safe schedulability of bounded-rate multi-mode systems. In Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control (HSCC’13). ACM, 243--252. Google Scholar
Digital Library
- Rajeev Alur, Ashutosh Trivedi, and Dominik Wojtczak. 2012. Optimal scheduling for constant-rate multi-mode systems. In Proceedings of the Conference on Hybrid Systems: Computation and Control (HSCC’12). ACM, 75--84. Google ScholarDigital Library
- Michael Ben-Or, Dexter Kozen, and John Reif. 1986. The complexity of elementary algebra and geometry. J. Comput. Syst. Sci. 32, 2 (1986), 251--264. Google ScholarDigital Library
- Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, and Jean-François Raskin. 2010. Generalized mean-payoff and energy games. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’10), Vol. 8. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 505--516.Google Scholar
- Bernard Chazelle. 1993. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10 (1993), 377--409. Google ScholarDigital Library
- David P. Dobkin and Steven P. Reiss. 1980. The complexity of linear programming. Theoret. Comput. Sci. 11, 1 (1980), 1--18. Google ScholarDigital Library
- Rod Downey and Michael Fellows. 1999. Parameterized Complexity. Springer.Google Scholar
- Laurent Doyen and Alexander Rabinovich. 2013. Robot Games. Research Report LSV-13-02. Laboratoire Spécification et Vérification, ENS Cachan, France. Retrieved from http://www.lsv.ens-cachan.fr/Publis/RAPPORTS_LSV/PDF/rr-lsv-2013-02.pdf.Google Scholar
- Solomon Feferman. 2006. Tarski’s influence on computer science. Logic. Methods Comput. Sci. 2, 3 (2006), 1--13.Google Scholar
- Michael J. Fischer and Michael O. Rabin. 1974. Super-exponential complexity of Presburger arithmetic. Massachusetts Institute of Technology, Cambridge, MA, USA. http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail&id===oai%3Ancstrlh%3Amitai%3AMIT-LCS%2F%2FMIT%2FLCS%2FTM-43. Google ScholarDigital Library
- D. Gale and F. M. Stewart. 1953. Infinite games with perfect information. Ann. Math. Studies 28 (1953), 245--266.Google Scholar
- Panos Giannopoulos, Christian Knauer, and Günter Rote. 2009. The parameterized complexity of some geometric problems in unbounded dimension. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC’09), Jianer Chen and Fedor V. Fomin (Eds.). Springer, 198--209. Google ScholarDigital Library
- Thomas A. Henzinger, Benjamin Horowitz, and Rupak Majumdar. 1999. Rectangular hybrid games. In Proceedings of the 10th International Conference on Concurrency Theory (CONCUR’99) (Lecture Notes in Computer Science), Vol. 1664. Springer, 320--335. Google ScholarDigital Library
- Thomas A. Henzinger and Peter W. Kopke. 1997. Discrete-time control for rectangular hybrid automata. In Proceedings of the 24th International Colloquium on Automata, Languages, and Programming (ICALP’97) (Lecture Notes in Computer Science), Vol. 1256. Springer, 582--593. Google ScholarDigital Library
- Marcin Jurdzinski, Ranko Lazic, and Sylvain Schmitz. 2015. Fixed-dimensional energy games are in pseudo-polynomial time. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15) (Lecture Notes in Computer Science), Vol. 9135. Springer, 260--272. Google ScholarDigital Library
- Christian Knauer, Stefan König, and Daniel Werner. 2015. Fixed-parameter complexity and approximability of norm maximization. Discrete Comput. Geom. 53, 2 (2015), 276--295. Google ScholarDigital Library
- Stéphane Le Roux and Arno Pauly. 2015. Finite choice, convex choice and finding roots. Logic. Methods Comput. Sci. 11, 4 (2015).Google Scholar
- Stéphane Le Roux, Arno Pauly, and Jean-François Raskin. 2017. Minkowski games. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS’17) (LIPIcs), Heribert Vollmer and Brigitte Valleé (Eds.), Vol. 66. Schloss Dagstuhl, 50:1--50:13.Google Scholar
- Oded Maler, Amir Pnueli, and Joseph Sifakis. 1995. On the Synthesis of Discrete Controllers for Timed Systems. Springer, Berlin, 229--242.Google Scholar
- Donald A. Martin. 1975. Borel determinacy. Ann. Math. 102, 2 (1975), pp. 363--371.Google ScholarCross Ref
- Marvin L. Minsky. 1961. Recursive unsolvability of Post’s problem of “Tag” and other topics in theory of Turing machines. Ann. Math. 74, 3 (1961), 437--455.Google ScholarCross Ref
- Reino Niskanen, Igor Potapov, and Julien Reichert. 2016. Undecidability of two-dimensional robot games. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS’16) (LIPIcs), Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier (Eds.), Vol. 58. Schloss Dagstuhl, 73:1--73:13.Google Scholar
- Christos H. Papadimitriou. 1981. On the complexity of integer programming. J. ACM 28, 4 (Oct. 1981), 765--768. Google ScholarDigital Library
- Arno Pauly. 2016. On the topological aspects of the theory of represented spaces. Computability 5, 2 (2016), 159--180.Google ScholarCross Ref
- Arno Pauly and Willem Fouché. 2017. How constructive is constructing measures? J. Logic Anal. 9 (2017). Retrieved from http://logicandanalysis.org/index.php/jla/issue/view/16.Google Scholar
- Amir Pnueli and Roni Rosner. 1989. On the synthesis of a reactive module. In Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages. ACM Press, 179--190. Google ScholarDigital Library
- Matthias Schröder. 2007. Admissible representations for probability measures. Math. Logic Quart. 53, 4 (2007), 431--445.Google ScholarCross Ref
- user141614 (https://math.stackexchange.com/users/141614/user141614). 2016. Absorbing convex hull into Minkowski sum. Mathematics Stack Exchange. Retrieved from https://math.stackexchange.com/q/1814457.Google Scholar
- Klaus Weihrauch. 2000. Computable Analysis. Springer-Verlag. Google ScholarDigital Library
- Philip Wolfe. 1955. The strict determinateness of certain infinite games. Pacific J. Math. 5 (1955), 841--847.Google ScholarCross Ref
- Martin Ziegler. 2004. Computable operators on regular sets. Math. Logic Quart. 50 (2004), 392--404.Google ScholarCross Ref
Index Terms
- Minkowski Games
Recommendations
Visibly Pushdown Automata and Transducers with Counters
Non-Classical Models of Automata and Applications VIWe generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and ...
Casual games discussion
Future Play '07: Proceedings of the 2007 conference on Future PlayDigital games have become a remarkable cultural phenomenon in the last ten years. The casual games sector especially has been growing rapidly in the last few years. However, there is no clear view on what is "casual" in games cultures and the area has ...
Comments