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

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
Department:
Unknown
Role:
Author
More from this funder
Grant:
“Reachabilityproblemsforwords,matrices
maps”(EP/M00077X/1
Publisher:
Springer, Cham Publisher's website
Journal:
DLT 2018: Developments in Language Theory Journal website
Volume:
11088
Pages:
465-477
Series:
Lecture Notes in Computer Science
Host title:
DLT 2018: Developments in Language Theory
Publication date:
2018-08-05
Acceptance date:
2018-06-08
DOI:
ISSN:
0302-9743
Source identifiers:
924809
ISBN:
9783319986531
Pubs id:
pubs:924809
UUID:
uuid:f69fe662-b4c4-43e6-b4a8-9caa4cde9ed5
Local pid:
pubs:924809
Deposit date:
2018-11-13

Terms of use


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