Niskanen, R ORCID: 0000-0002-2210-1481, Potapov, I and Reichert, J
(2020)
On decidability and complexity of low-dimensional robot games.
Journal of Computer and System Sciences, 107.
pp. 124-141.
Text
NPR_revision.pdf - Author Accepted Manuscript Download (555kB) | Preview |
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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Reachability games, Vector addition game, Decidability, Winning strategy, Integer vector addition system |
Depositing User: | Symplectic Admin |
Date Deposited: | 22 Aug 2019 10:01 |
Last Modified: | 19 Jan 2023 00:28 |
DOI: | 10.1016/j.jcss.2019.08.003 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3052304 |