On affine reachability problems
We analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, hence PSPACE-complete, strengthening a result by Finkel et al. that required polynomial updates. Building on recent resul...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl
2020
|
| _version_ | 1826297069670760448 |
|---|---|
| author | Jaax, S Kiefer, S |
| author_facet | Jaax, S Kiefer, S |
| author_sort | Jaax, S |
| collection | OXFORD |
| description | We analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, hence PSPACE-complete, strengthening a result by Finkel et al. that required polynomial updates. Building on recent results on two-dimensional integer matrices, we prove NP-completeness of the mortality problem for 2-dimensional integer matrices with determinants +1 and 0. Motivated by tight connections with 1-dimensional affine reachability problems without control states, we also study the complexity of a number of reachability problems in finitely generated semigroups of 2-dimensional upper-triangular integer matrices. |
| first_indexed | 2024-03-07T04:26:00Z |
| format | Conference item |
| id | oxford-uuid:cca1dc8e-5f4f-4486-b4bd-55ea9864ef45 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:26:00Z |
| publishDate | 2020 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:cca1dc8e-5f4f-4486-b4bd-55ea9864ef452022-03-27T07:23:22ZOn affine reachability problemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:cca1dc8e-5f4f-4486-b4bd-55ea9864ef45EnglishSymplectic ElementsSchloss Dagstuhl2020Jaax, SKiefer, SWe analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, hence PSPACE-complete, strengthening a result by Finkel et al. that required polynomial updates. Building on recent results on two-dimensional integer matrices, we prove NP-completeness of the mortality problem for 2-dimensional integer matrices with determinants +1 and 0. Motivated by tight connections with 1-dimensional affine reachability problems without control states, we also study the complexity of a number of reachability problems in finitely generated semigroups of 2-dimensional upper-triangular integer matrices. |
| spellingShingle | Jaax, S Kiefer, S On affine reachability problems |
| title | On affine reachability problems |
| title_full | On affine reachability problems |
| title_fullStr | On affine reachability problems |
| title_full_unstemmed | On affine reachability problems |
| title_short | On affine reachability problems |
| title_sort | on affine reachability problems |
| work_keys_str_mv | AT jaaxs onaffinereachabilityproblems AT kiefers onaffinereachabilityproblems |