Journal article 773 views 294 downloads
Minkowski Games
Stéphane Le Roux,
Arno Pauly 
,
Jean-François Raskin
,
Jean-François Raskin
ACM Transactions on Computational Logic, Volume: 19, Issue: 3, Pages: 1 - 29
Swansea University Author:
Arno Pauly
-
PDF | Accepted Manuscript
Download (325.37KB)
DOI (Published version): 10.1145/3230741
Abstract
We introduce and study Minkowski games. These are two player games, where the 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, and the other wants to escape to infinity; as well as safety game...
| Published in: | ACM Transactions on Computational Logic |
|---|---|
| ISSN: | 1529-3785 1557-945X |
| Published: |
Association for Computing Machinery (ACM)
2018
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa40809 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
We introduce and study Minkowski games. These are two player games, where the 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, 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. |
|---|---|
| Keywords: |
game theory; verification of hybrid systems; polytopes |
| College: |
Faculty of Science and Engineering |
| Issue: |
3 |
| Start Page: |
1 |
| End Page: |
29 |