On reachability problems for low dimensional matrix semigroups

02/25/2019
by   Thomas Colcombet, et al.
0

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

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset