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.