Reachability games and related matrix and word problems

Niskanen, R ORCID: 0000-0002-2210-1481 (2018) Reachability games and related matrix and word problems. Doctor of Philosophy thesis, University of Liverpool.

Text 201052026_Feb2018.pdf - Unspecified Download (4MB)

Abstract

In this thesis, we study different two-player zero-sum games, where one player, called Eve, has a reachability objective (i.e., aims to reach a particular configuration) and the other, called Adam, has a safety objective (i.e., aims to avoid the configuration). We study a general class of games, called Attacker-Defender games, where the computational environment can vary from as simple as the integer line to n-dimensional topological braids. Similarly, the moves themselves can be simple vector addition or linear transformations defined by matrices. The main computational problem is to decide whether Eve has a winning strategy to reach the target configuration from the initial configuration, or whether the dual holds, that is, whether Adam can ensure that the target is never reached. The notion of a winning strategy is widely used in game semantics and its existence means that the player can ensure that his or her winning conditions are met, regardless of the actions of the opponent. It general, games provide a powerful framework to model and analyse interactive processes with uncontrollable adversaries. We formulated several Attacker-Defender games played on different mathematical domains with different transformations (moves), and identified classes of games, where the checking for existence of a winning strategy is undecidable. In other classes, where the problem is decidable, we established their computational complexity. In the thesis, we investigate four classes of games where determining the winner is undecidable: word games, where the players' moves are words over a group alphabet together with integer weights or where the moves are pairs of words over group alphabets; matrix games on vectors, where players transform a three-dimensional vector by linear transformations defined by 3×3 integer matrices; braid games, where players braid and unbraid a given braid; and last, but not least, games played on two-dimensional Z-VAS, closing the gap between decidable and undecidable cases and answering an existing open problem of the field. We also identified decidable fragments, such as word games, where the moves are over a single group alphabet, games on one-dimensional Z-VASS. For word games, we provide an upper-bound of EXPTIME , while for games on Z-VASS, tight bounds of EXPTIME-complete or EXPSPACE-complete, depending on the state structure. We also investigate single-player systems such as polynomial iteration and identity problem in matrix semigroups. We show that the reachability problem for polynomial iteration is PSPACE-complete while the identity problem for the Heisenberg group is in PTIME for dimension three and in EXPTIME for higher dimensions.

Item Type:	Thesis (Doctor of Philosophy)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	14 Aug 2018 06:57
Last Modified:	16 Jan 2024 17:21
DOI:	10.17638/03018108
Supervisors:	Potapov, Igor Halava, Vesa Spirakis, Paul ORCID: 0000-0001-5396-3749
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3018108