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...
| Hlavní autoři: | , , , |
|---|---|
| Médium: | Conference item |
| Vydáno: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
|
| _version_ | 1826274535617331200 |
|---|---|
| author | Colcombet, T Ouaknine, J Semukhin, P Worrell, J |
| author_facet | Colcombet, T Ouaknine, J Semukhin, P Worrell, J |
| author_sort | Colcombet, T |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T22:44:55Z |
| format | Conference item |
| id | oxford-uuid:5cd6d08a-ce76-45a2-b7c1-a9e48f02b6e0 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:44:55Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:5cd6d08a-ce76-45a2-b7c1-a9e48f02b6e02022-03-26T17:30:39ZOn reachability problems for low-dimensional matrix semigroupsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:5cd6d08a-ce76-45a2-b7c1-a9e48f02b6e0Symplectic Elements at OxfordSchloss Dagstuhl - Leibniz-Zentrum für Informatik2019Colcombet, TOuaknine, JSemukhin, PWorrell, JWe 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. |
| spellingShingle | Colcombet, T Ouaknine, J Semukhin, P Worrell, J On reachability problems for low-dimensional matrix semigroups |
| title | On reachability problems for low-dimensional matrix semigroups |
| title_full | On reachability problems for low-dimensional matrix semigroups |
| title_fullStr | On reachability problems for low-dimensional matrix semigroups |
| title_full_unstemmed | On reachability problems for low-dimensional matrix semigroups |
| title_short | On reachability problems for low-dimensional matrix semigroups |
| title_sort | on reachability problems for low dimensional matrix semigroups |
| work_keys_str_mv | AT colcombett onreachabilityproblemsforlowdimensionalmatrixsemigroups AT ouakninej onreachabilityproblemsforlowdimensionalmatrixsemigroups AT semukhinp onreachabilityproblemsforlowdimensionalmatrixsemigroups AT worrellj onreachabilityproblemsforlowdimensionalmatrixsemigroups |