{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:14Z","timestamp":1750221074507,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC inVEST","award":["279499"],"award-info":[{"award-number":["279499"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2018,7,31]]},"abstract":"<jats:p>We introduce and study Minkowski games. These are two-player games, where the players take turns to choose positions in R&lt;sup&lt;d&lt;\/sup&lt; 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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3230741","type":"journal-article","created":{"date-parts":[[2018,9,4]],"date-time":"2018-09-04T12:37:30Z","timestamp":1536064650000},"page":"1-29","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Minkowski Games"],"prefix":"10.1145","volume":"19","author":[{"given":"St\u00e9phane Le","family":"Roux","sequence":"first","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgique"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-0173-3295","authenticated-orcid":false,"given":"Arno","family":"Pauly","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgique"}]},{"given":"Jean-Fran\u00e7ois","family":"Raskin","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgique"}]}],"member":"320","published-online":{"date-parts":[[2018,8,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461328.2461366"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185632.2185647"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90029-2"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201910)","volume":"8","author":"Chatterjee Krishnendu","year":"2010","unstructured":"Krishnendu Chatterjee , Laurent Doyen , Thomas A. Henzinger , and Jean-Fran\u00e7ois 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\u201910) , Vol. 8 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 505--516. Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, and Jean-Fran\u00e7ois 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\u201910), Vol. 8. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 505--516."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573985"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90031-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Rod Downey and Michael Fellows. 1999. Parameterized Complexity. Springer.  Rod Downey and Michael Fellows. 1999. Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"Tarski\u2019s influence on computer science","volume":"2","author":"Feferman Solomon","year":"2006","unstructured":"Solomon Feferman . 2006 . Tarski\u2019s influence on computer science . Logic. Methods Comput. Sci. 2 , 3 (2006), 1 -- 13 . Solomon Feferman. 2006. Tarski\u2019s influence on computer science. Logic. Methods Comput. Sci. 2, 3 (2006), 1--13.","journal-title":"Logic. Methods Comput. Sci."},{"key":"e_1_2_1_10_1","volume-title":"Rabin","author":"Fischer Michael J.","year":"1974","unstructured":"Michael J. Fischer and Michael O . Rabin . 1974 . Super-exponential complexity of Presburger arithmetic. Massachusetts Institute of Technology , Cambridge, MA, USA. https:\/\/2.zoppoz.workers.dev:443\/http\/www.ncstrl.org:8900\/ncstrl\/servlet\/search?formname&equals;detail&id&equals;&equals;&equals;oai%3Ancstrlh%3Amitai%3AMIT-LCS%2F%2FMIT%2FLCS%2FTM-43. Michael J. Fischer and Michael O. Rabin. 1974. Super-exponential complexity of Presburger arithmetic. Massachusetts Institute of Technology, Cambridge, MA, USA. https:\/\/2.zoppoz.workers.dev:443\/http\/www.ncstrl.org:8900\/ncstrl\/servlet\/search?formname&equals;detail&id&equals;&equals;&equals;oai%3Ancstrlh%3Amitai%3AMIT-LCS%2F%2FMIT%2FLCS%2FTM-43."},{"key":"e_1_2_1_11_1","first-page":"245","article-title":"Infinite games with perfect information","volume":"28","author":"Gale D.","year":"1953","unstructured":"D. Gale and F. M. Stewart . 1953 . Infinite games with perfect information . Ann. Math. Studies 28 (1953), 245 -- 266 . D. Gale and F. M. Stewart. 1953. Infinite games with perfect information. Ann. Math. Studies 28 (1953), 245--266.","journal-title":"Ann. Math. Studies"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_16"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646734.701483"},{"key":"e_1_2_1_14_1","volume-title":"Kopke","author":"Henzinger Thomas A.","year":"1997","unstructured":"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\u201997) (Lecture Notes in Computer Science), Vol. 1256 . Springer , 582--593. 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\u201997) (Lecture Notes in Computer Science), Vol. 1256. Springer, 582--593."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_21"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9667-0"},{"key":"e_1_2_1_17_1","volume-title":"Finite choice, convex choice and finding roots. Logic. Methods Comput. Sci. 11, 4","author":"Roux St\u00e9phane Le","year":"2015","unstructured":"St\u00e9phane Le Roux and Arno Pauly . 2015. Finite choice, convex choice and finding roots. Logic. Methods Comput. Sci. 11, 4 ( 2015 ). St\u00e9phane Le Roux and Arno Pauly. 2015. Finite choice, convex choice and finding roots. Logic. Methods Comput. Sci. 11, 4 (2015)."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS\u201917)","volume":"66","author":"Roux St\u00e9phane Le","year":"2017","unstructured":"St\u00e9phane Le Roux , Arno Pauly , and Jean-Fran\u00e7ois Raskin . 2017 . Minkowski games . In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS\u201917) (LIPIcs), Heribert Vollmer and Brigitte Valle\u00e9 (Eds.) , Vol. 66 . Schloss Dagstuhl, 50:1--50:13. St\u00e9phane Le Roux, Arno Pauly, and Jean-Fran\u00e7ois Raskin. 2017. Minkowski games. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS\u201917) (LIPIcs), Heribert Vollmer and Brigitte Valle\u00e9 (Eds.), Vol. 66. Schloss Dagstuhl, 50:1--50:13."},{"volume-title":"On the Synthesis of Discrete Controllers for Timed Systems","author":"Maler Oded","key":"e_1_2_1_19_1","unstructured":"Oded Maler , Amir Pnueli , and Joseph Sifakis . 1995. On the Synthesis of Discrete Controllers for Timed Systems . Springer , Berlin , 229--242. Oded Maler, Amir Pnueli, and Joseph Sifakis. 1995. On the Synthesis of Discrete Controllers for Timed Systems. Springer, Berlin, 229--242."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971035"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916)","volume":"58","author":"Niskanen Reino","year":"2016","unstructured":"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\u201916) (LIPIcs), Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier (Eds.) , Vol. 58 . Schloss Dagstuhl, 73:1--73:13. 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\u201916) (LIPIcs), Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier (Eds.), Vol. 58. Schloss Dagstuhl, 73:1--73:13."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322287"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.3233\/COM-150049"},{"key":"e_1_2_1_25_1","volume-title":"How constructive is constructing measures? J. Logic Anal. 9","author":"Pauly Arno","year":"2017","unstructured":"Arno Pauly and Willem Fouch\u00e9 . 2017. How constructive is constructing measures? J. Logic Anal. 9 ( 2017 ). Retrieved from https:\/\/2.zoppoz.workers.dev:443\/http\/logicandanalysis.org\/index.php\/jla\/issue\/view\/16. Arno Pauly and Willem Fouch\u00e9. 2017. How constructive is constructing measures? J. Logic Anal. 9 (2017). Retrieved from https:\/\/2.zoppoz.workers.dev:443\/http\/logicandanalysis.org\/index.php\/jla\/issue\/view\/16."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200710010"},{"key":"e_1_2_1_28_1","unstructured":"user141614 (https:\/\/2.zoppoz.workers.dev:443\/https\/math.stackexchange.com\/users\/141614\/user141614). 2016. Absorbing convex hull into Minkowski sum. Mathematics Stack Exchange. Retrieved from https:\/\/2.zoppoz.workers.dev:443\/https\/math.stackexchange.com\/q\/1814457.  user141614 (https:\/\/2.zoppoz.workers.dev:443\/https\/math.stackexchange.com\/users\/141614\/user141614). 2016. Absorbing convex hull into Minkowski sum. Mathematics Stack Exchange. Retrieved from https:\/\/2.zoppoz.workers.dev:443\/https\/math.stackexchange.com\/q\/1814457."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/358357"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.841"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310107"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3230741","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3230741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:30Z","timestamp":1750208250000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3230741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,31]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7,31]]}},"alternative-id":["10.1145\/3230741"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/3230741","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2018,7,31]]},"assertion":[{"value":"2007-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}