Ko, SK, Niskanen, R ORCID: 0000-0002-2210-1481 and Potapov, I
(2021)
Reachability problems in low-dimensional nondeterministic polynomial maps over integers.
INFORMATION AND COMPUTATION, 281.
p. 104785.
Text
polynomial_maps_elements.pdf - Author Accepted Manuscript Download (530kB) | Preview |
Abstract
We study reachability problems for various nondeterministic polynomial maps in Zn. We prove that the reachability problem for very simple three-dimensional affine maps (with independent variables) is undecidable and is PSPACE-hard for both two-dimensional affine maps and one-dimensional quadratic maps. Then we show that the complexity of the reachability problem for maps without functions of the form ±x+a0 is lower. In this case the reachability problem is PSPACE for any dimension and if the dimension is not fixed, then the problem is PSPACE-complete. Finally we extend the model by considering maps as language acceptors and prove that the universality problem is undecidable for two-dimensional affine maps.
Item Type: | Article |
---|---|
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 28 Jun 2021 09:37 |
Last Modified: | 18 Jan 2023 21:37 |
DOI: | 10.1016/j.ic.2021.104785 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3127989 |