Decidability of membership problems for flat rational subsets of GL (2, Q) and singular matrices
<p>This work relates numerical problems on matrices over the rationals to symbolic algorithms on words and finite automata. Using exact algebraic algorithms and symbolic computation, we prove new decidability results for 2 × 2 matrices over Q. Namely, we introduce a notion of flat rational set...
| मुख्य लेखकों: | , , |
|---|---|
| स्वरूप: | Conference item |
| भाषा: | English |
| प्रकाशित: |
Association for Computing Machinery
2020
|
| _version_ | 1826289810728288256 |
|---|---|
| author | Diekert, V Potapov, I Semukhin, P |
| author_facet | Diekert, V Potapov, I Semukhin, P |
| author_sort | Diekert, V |
| collection | OXFORD |
| description | <p>This work relates numerical problems on matrices over the rationals to symbolic algorithms on words and finite automata. Using exact algebraic algorithms and symbolic computation, we prove new decidability results for 2 × 2 matrices over Q. Namely, we introduce a notion of flat rational sets: if M is a monoid and N ≤ M is its submonoid, then flat rational sets of M relative to N are finite unions of the form L0g1L1 ··· gtLt where all Lis are rational subsets of N and gi ∈ M. We give quite general sufficient conditions under which flat rational sets form an effective relative Boolean algebra. As a corollary, we obtain that the emptiness problem for Boolean combinations of flat rational subsets of GL(2, Q) over GL(2, Z) is decidable.</p>
<p>We also show a dichotomy for nontrivial group extension of GL(2, Z) in GL(2, Q): if G is a f.g. group such that GL(2, Z) < G ≤ GL(2, Q), then either G ≅ GL(2, Z) × Zk, for some k ≥ 1, or G contains an extension of the Baumslag-Solitar group BS(1, q), with q ≥ 2, of infinite index. It turns out that in the first case the membership problem for G is decidable but the equality problem for rational subsets of G is undecidable. In the second case, decidability of the membership problem is open for every such G. In the last section we prove new decidability results for flat rational sets that contain singular matrices. In particular, we show that the membership problem is decidable for flat rational subsets of M(2, Q) relative to the submonoid that is generated by the matrices from M(2, Z) with determinants 0, ± 1 and the central rational matrices.</p> |
| first_indexed | 2024-03-07T02:34:35Z |
| format | Conference item |
| id | oxford-uuid:a85c1b2d-85dc-4f23-b509-e64c16ac3dea |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T02:34:35Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:a85c1b2d-85dc-4f23-b509-e64c16ac3dea2022-03-27T03:01:04ZDecidability of membership problems for flat rational subsets of GL (2, Q) and singular matricesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a85c1b2d-85dc-4f23-b509-e64c16ac3deaEnglishSymplectic ElementsAssociation for Computing Machinery2020Diekert, VPotapov, ISemukhin, P<p>This work relates numerical problems on matrices over the rationals to symbolic algorithms on words and finite automata. Using exact algebraic algorithms and symbolic computation, we prove new decidability results for 2 × 2 matrices over Q. Namely, we introduce a notion of flat rational sets: if M is a monoid and N ≤ M is its submonoid, then flat rational sets of M relative to N are finite unions of the form L0g1L1 ··· gtLt where all Lis are rational subsets of N and gi ∈ M. We give quite general sufficient conditions under which flat rational sets form an effective relative Boolean algebra. As a corollary, we obtain that the emptiness problem for Boolean combinations of flat rational subsets of GL(2, Q) over GL(2, Z) is decidable.</p> <p>We also show a dichotomy for nontrivial group extension of GL(2, Z) in GL(2, Q): if G is a f.g. group such that GL(2, Z) < G ≤ GL(2, Q), then either G ≅ GL(2, Z) × Zk, for some k ≥ 1, or G contains an extension of the Baumslag-Solitar group BS(1, q), with q ≥ 2, of infinite index. It turns out that in the first case the membership problem for G is decidable but the equality problem for rational subsets of G is undecidable. In the second case, decidability of the membership problem is open for every such G. In the last section we prove new decidability results for flat rational sets that contain singular matrices. In particular, we show that the membership problem is decidable for flat rational subsets of M(2, Q) relative to the submonoid that is generated by the matrices from M(2, Z) with determinants 0, ± 1 and the central rational matrices.</p> |
| spellingShingle | Diekert, V Potapov, I Semukhin, P Decidability of membership problems for flat rational subsets of GL (2, Q) and singular matrices |
| title | Decidability of membership problems for flat rational subsets of GL (2, Q) and singular matrices |
| title_full | Decidability of membership problems for flat rational subsets of GL (2, Q) and singular matrices |
| title_fullStr | Decidability of membership problems for flat rational subsets of GL (2, Q) and singular matrices |
| title_full_unstemmed | Decidability of membership problems for flat rational subsets of GL (2, Q) and singular matrices |
| title_short | Decidability of membership problems for flat rational subsets of GL (2, Q) and singular matrices |
| title_sort | decidability of membership problems for flat rational subsets of gl 2 q and singular matrices |
| work_keys_str_mv | AT diekertv decidabilityofmembershipproblemsforflatrationalsubsetsofgl2qandsingularmatrices AT potapovi decidabilityofmembershipproblemsforflatrationalsubsetsofgl2qandsingularmatrices AT semukhinp decidabilityofmembershipproblemsforflatrationalsubsetsofgl2qandsingularmatrices |