Conference item icon

Conference item

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 PSPACE-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 PSPACE-complete in general, and NP-hard for any fixed dimension. Fina...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1007/978-3-319-98654-8_38

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More from this funder
Grant:
“Reachability problems for words, matrices and maps” (EP/M00077X/1)
Publisher:
Springer, Cham Publisher's website
Volume:
11088
Pages:
465-477
Series:
Lecture Notes in Computer Science
Publication date:
2018-08-05
Acceptance date:
2018-06-08
DOI:
ISSN:
0302-9743
Pubs id:
pubs:924809
URN:
uri:f69fe662-b4c4-43e6-b4a8-9caa4cde9ed5
UUID:
uuid:f69fe662-b4c4-43e6-b4a8-9caa4cde9ed5
Local pid:
pubs:924809
ISBN:
9783319986531

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP