On Reachability Problems for Low-Dimensional Matrix Semigroups
Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, James Worrell · arXiv (Cornell University) · 2019
We consider the Membership and the Half-Space Reachability problems for matrices in dimensions two and three. Our first main result is that the Membership Problem is decidable for finitely generated sub-semigroups of the Heisenberg group over rational numbers. Furthermore, we prove two decidability results for the Half-Space Reachability Problem. Namely, we show that this problem is decidable for sub-semigroups of GL(2,Z) and of the Heisenberg group over rational numbers.