Safety and Reachability in k-Control Games on Integer Vector Addition Systems with States

Niskanen, R ORCID: 0000-0002-2210-1481, Potapov, I and Topley, J Safety and Reachability in k-Control Games on Integer Vector Addition Systems with States. In: Computability in Europe 2026, 26th Jul- 31st Jul 2026, Trier, Germany. (Accepted)

Text Safety and Reachability in k-Control Games on Integer Vector Addition Systems with States.pdf - Accepted Version Access Restricted Download (411kB)

Abstract

Integer vector addition systems with states (Z-VASSs) are vector addition systems with states, where the configurations are from Zd. Two-player games on Z-VASS are known to be undecidable when played on two-dimensional Z-VAS(S)s. Here, we study a restricted variant of the game, where one of the players, Adam, can play k non-zero moves from his move set. Adam’s (safety) goal is to ensure that the other player, Eve, cannot reach a particular point in the space. We show that, for any dimension, deciding whether Eve has a winning strategy is in NEXPTIME and is NP-hard if k is part of the input. Additionally, we extend the safety objective from a single point to a hyperplane and prove that the complexity does not increase. We also study the dual variant (reachability), where Eve’s resources are limited and show that deciding whether Eve has a winning strategy is also in EXPTIME. On the other hand, if k is fixed, safety in k-control games is NP-complete, while reachability is in PTIME.

Item Type:	Conference or Workshop Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Computer software
Divisions:	Computer Science and Mathematics
Date of acceptance:	27 April 2026
Date Deposited:	04 Jun 2026 14:31
Last Modified:	04 Jun 2026 14:31
URI:	https://researchonline.ljmu.ac.uk/id/eprint/28735

View Item