Reachability problems in nondeterministic polynomial maps on the integers

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 PSPACE-hard for two-dimensional quadratic maps. Then we show that the complexi...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron: Ko, SK, Niskanen, R, Potapov, I
Fformat: Conference item
Cyhoeddwyd: Springer, Cham 2018