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...
| Հիմնական հեղինակներ: | , , |
|---|---|
| Ձևաչափ: | Conference item |
| Հրապարակվել է: |
Springer, Cham
2018
|
| _version_ | 1826305440775929856 |
|---|---|
| author | Ko, SK Niskanen, R Potapov, I |
| author_facet | Ko, SK Niskanen, R Potapov, I |
| author_sort | Ko, SK |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T06:32:54Z |
| format | Conference item |
| id | oxford-uuid:f69fe662-b4c4-43e6-b4a8-9caa4cde9ed5 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:32:54Z |
| publishDate | 2018 |
| publisher | Springer, Cham |
| record_format | dspace |
| spelling | oxford-uuid:f69fe662-b4c4-43e6-b4a8-9caa4cde9ed52022-03-27T12:36:26ZReachability problems in nondeterministic polynomial maps on the integersConference itemhttp://purl.org/coar/resource_type/c_5794uuid:f69fe662-b4c4-43e6-b4a8-9caa4cde9ed5Symplectic Elements at OxfordSpringer, Cham2018Ko, SKNiskanen, RPotapov, IWe 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. |
| spellingShingle | Ko, SK Niskanen, R Potapov, I Reachability problems in nondeterministic polynomial maps on the integers |
| title | Reachability problems in nondeterministic polynomial maps on the integers |
| title_full | Reachability problems in nondeterministic polynomial maps on the integers |
| title_fullStr | Reachability problems in nondeterministic polynomial maps on the integers |
| title_full_unstemmed | Reachability problems in nondeterministic polynomial maps on the integers |
| title_short | Reachability problems in nondeterministic polynomial maps on the integers |
| title_sort | reachability problems in nondeterministic polynomial maps on the integers |
| work_keys_str_mv | AT kosk reachabilityproblemsinnondeterministicpolynomialmapsontheintegers AT niskanenr reachabilityproblemsinnondeterministicpolynomialmapsontheintegers AT potapovi reachabilityproblemsinnondeterministicpolynomialmapsontheintegers |