Journal article
On decidability and complexity of low-dimensional robot games
- Abstract:
- A robot game, also known as a Z-VAS game, is a two-player vector addition game played on the integer lattice Zn, where one of the players, Adam, aims to avoid the origin while the other player, Eve, aims to reach the origin. The problem is to decide whether or not Eve has a winning strategy. In this paper we prove undecidability of the two-dimensional robot game closing the gap between undecidable and decidable cases. We also prove that deciding the winner in a robot game with states in dimension one is EXPSPACE-complete and study a subclass of robot games where deciding the winner is in EXPTIME.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 542.6KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jcss.2019.08.003
Authors
- Publisher:
- Elsevier
- Journal:
- Journal of Computer and System Sciences More from this journal
- Volume:
- 107
- Issue:
- February 2020
- Pages:
- 124-141
- Publication date:
- 2019-08-20
- Acceptance date:
- 2019-08-09
- DOI:
- ISSN:
-
0022-0000
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:1047968
- UUID:
-
uuid:a63d3805-648d-41da-b21b-88d4dbd304d3
- Local pid:
-
pubs:1047968
- Source identifiers:
-
1047968
- Deposit date:
-
2019-08-28
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier
- Copyright date:
- 2019
- Rights statement:
- © 2019 Elsevier Inc. All rights reserved.
- Notes:
- This is the accepted manuscript version of the article. The final version is available from Elsevier at: https://doi.org/10.1016/j.jcss.2019.08.003
If you are the owner of this record, you can report an update to it here: Report update to this record