License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.50
URN: urn:nbn:de:0030-drops-69849
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6984/
Le Roux, Stéphane ;
Pauly, Arno ;
Raskin, Jean-François
Minkowski Games
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.
BibTeX - Entry
@InProceedings{leroux_et_al:LIPIcs:2017:6984,
author = {St{\'e}phane Le Roux and Arno Pauly and Jean-Fran{\c{c}}ois Raskin},
title = {{Minkowski Games}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {50:1--50:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-028-6},
ISSN = {1868-8969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6984},
URN = {urn:nbn:de:0030-drops-69849},
doi = {10.4230/LIPIcs.STACS.2017.50},
annote = {Keywords: Control in R^d, determinacy, polytopic/arbitrary, coNP-complete, undecidable}
}
|
Keywords: |
|
Control in R^d, determinacy, polytopic/arbitrary, coNP-complete, undecidable |
|
Collection: |
|
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
06.03.2017 |
