On Affine Reachability Problems.

We analyze affine reachability problems in dimensions 1 and 2. On the one hand, 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. On the other hand, motivated by tight connections with 1-dimensional affine reachability problems without control states, we study algorithmic problems in finitely generated semigroups of 2-dimensional upper-triangular integer matrices. Building on a variety of techniques from recent years, we obtain a number of complexity results, including NP-completeness of the mortality problem for matrices with determinants +1 and 0.