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.
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 |