## 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