On decidability and complexity of low-dimensional robot games



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. 124 - 141.

[img] Text
NPR_revision.pdf - Accepted Version

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: 27 Apr 2022 15:14
DOI: 10.1016/j.jcss.2019.08.003
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3052304