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. Finally we extend the model by considering maps as language acceptors and prove that the universality problem is undecidable for two-dimensional affine maps.
Publication status:
Published
Peer review status:
Peer reviewed

Actions

  • Cite

  • Print

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
Host title:
DLT 2018: Developments in Language Theory
Journal:
DLT 2018: Developments in Language Theory More from this journal
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
ISBN:
9783319986531

Pubs id:
pubs:924809
UUID:
uuid:f69fe662-b4c4-43e6-b4a8-9caa4cde9ed5
Local pid:
pubs:924809
Source identifiers:
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