%0 Conference Paper %1 DBLP:conf/mfcs/JaaxK20 %A Jaax, Stefan %A Kiefer, Stefan %B MFCS %D 2020 %E Esparza, Javier %E Král', Daniel %I Schloss Dagstuhl - Leibniz-Zentrum für Informatik %K conference %P 48:1--48:14 %R 10.4230/LIPIcs.MFCS.2020.48 %T On Affine Reachability Problems %U https://doi.org/10.4230/LIPIcs.MFCS.2020.48 %V 170 %X 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.

@inproceedings{DBLP:conf/mfcs/JaaxK20, abstract = {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. }, added-at = {2020-09-21T11:21:35.000+0200}, author = {Jaax, Stefan and Kiefer, Stefan}, bibsource = {dblp computer science bibliography, https://dblp.org}, biburl = {https://www.bibsonomy.org/bibtex/25afbe23564e44609291aaf55ee9e19a8/paves}, booktitle = {MFCS}, doi = {10.4230/LIPIcs.MFCS.2020.48}, editor = {Esparza, Javier and Kr{\'{a}}l', Daniel}, interhash = {6067abe56050c928c405ecdf1e453174}, intrahash = {5afbe23564e44609291aaf55ee9e19a8}, keywords = {conference}, note = {Preprint: <a href="https://arxiv.org/abs/1905.05114">Link</a><br>#conference}, pages = {48:1--48:14}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, series = {LIPIcs}, timestamp = {2023-09-24T19:44:11.000+0200}, title = {On Affine Reachability Problems}, url = {https://doi.org/10.4230/LIPIcs.MFCS.2020.48}, volume = 170, year = 2020 }