On reachability problems for low-dimensional matrix semigroups

Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell

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 fintely 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.

Proceedings of ICALP 19, LIPIcs 132, 2019. 15 pages.

PDF © 2019 Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell.



Imprint / Data Protection