@inproceedings{c819b3d53dd84419955dad4c23af1beb,
title = "Reachability Problems in Nondeterministic Polynomial Maps on the Integers",
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.",
author = "Ko, {Sang Ki} and Reino Niskanen and Igor Potapov",
note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; 22nd International Conference on Developments in Language Theory, DLT 2018 ; Conference date: 10-09-2018 Through 14-09-2018",
year = "2018",
doi = "10.1007/978-3-319-98654-8_38",
language = "English",
isbn = "9783319986531",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "465--477",
editor = "Mizuho Hoshi and Shinnosuke Seki",
booktitle = "Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings",
address = "Germany",
}