Reachability Problems in Nondeterministic Polynomial Maps on the Integers



Ko, Sang-Ki, Niskanen, Reino ORCID: 0000-0002-2210-1481 and Potapov, Igor
(2018) Reachability Problems in Nondeterministic Polynomial Maps on the Integers. In: 22nd International Conference on Developments in Language Theory (DLT 2018), 2018-9-10 - 2018-9-14, Tokyo, Japan.

[img] Text
paper_26.pdf - Author Accepted Manuscript

Download (390kB)

Abstract

We study the reachability problems in 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 PSAPCE -hard for two-dimensional quadratic maps. Then we show that the complexity of the reachability problem for maps without functions of the form x+b is lower. In this case the reachability problem is PSAPCE -complete in general, and NP -hard for any fixed dimension. 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: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 20 Jul 2018 10:32
Last Modified: 22 Feb 2023 16:22
DOI: 10.1007/978-3-319-98654-8_38
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3023984