On reachability problems for low-dimensional matrix semigroups
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...
| 主要な著者: | , , , |
|---|---|
| フォーマット: | Conference item |
| 出版事項: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
|
| 要約: | 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. |
|---|