2026-07-26T05:32:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10620 2024-03-06T10:46:18Z ddc:004 open_access

On Reachability Problems for Low-Dimensional Matrix Semigroups Colcombet, Thomas Ouaknine, Joël Semukhin, Pavel Worrell, James membership problem half-space reachability problem matrix semigroups Heisenberg group general linear group 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,Z) and of the Heisenberg group over rational numbers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Colcombet and Joël Ouaknine and Pavel Semukhin and James Worrell 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.44 urn:nbn:de:0030-drops-106209 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.44 eng https://creativecommons.org/licenses/by/3.0/legalcode