2019/02/28 by Thomas Colcombet, Joël Ouaknine, Pavel Semukhin +1 · 1 citation
Computer Science · #cs.CC #cs.FL
paper · pdf · doi:10.4230/lipics.icalp.2019.39
Full version of the paper submitted to ICALP 2019
arxiv created 2019/04/29 · arxiv updated 2019/04/30
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,ℤ) and of the Heisenberg group over rational numbers.