Facial reconstruction

Search LJMU Research Online

Browse Repository | Browse E-Theses

Reachability problems in low-dimensional nondeterministic polynomial maps over integers

Ko, SK, Niskanen, R and Potapov, I (2021) Reachability problems in low-dimensional nondeterministic polynomial maps over integers. Information and Computation, 281. ISSN 0890-5401

[img]
Preview
Text
Reachability problems in low-dimensional nondeterministic polynomial maps over integers.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

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
Uncontrolled Keywords: COMPLEXITY; Computer Science; Computer Science, Theory & Methods; Mathematics; Mathematics, Applied; MORTALITY; Physical Sciences; Science & Technology; SYSTEMS; Technology; TIME; UNDECIDABILITY BOUNDS; Science & Technology; Technology; Physical Sciences; Computer Science, Theory & Methods; Mathematics, Applied; Computer Science; Mathematics; UNDECIDABILITY BOUNDS; SYSTEMS; COMPLEXITY; MORTALITY; TIME; 08 Information and Computing Sciences; Computation Theory & Mathematics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Computer Science & Mathematics
Publisher: Elsevier
SWORD Depositor: A Symplectic
Date Deposited: 09 Jan 2023 13:21
Last Modified: 09 Jan 2023 13:30
DOI or ID number: 10.1016/j.ic.2021.104785
URI: https://researchonline.ljmu.ac.uk/id/eprint/18574
View Item View Item