Membership problem in GL(2, Z) extended by singular matrices
<p>We consider the membership problem for matrix semigroups, which is the problem to decide whether a matrix belongs to a given finitely generated matrix semigroup.</p> <br/> <p>In general, the decidability and complexity of this problem for two-dimensional matrix semigroups...
| Main Authors: | , |
|---|---|
| Formato: | Conference item |
| Publicado: |
Schloss Dagstuhl
2017
|
| _version_ | 1826302084972019712 |
|---|---|
| author | Potapov, I Semukhin, P |
| author_facet | Potapov, I Semukhin, P |
| author_sort | Potapov, I |
| collection | OXFORD |
| description | <p>We consider the membership problem for matrix semigroups, which is the problem to decide whether a matrix belongs to a given finitely generated matrix semigroup.</p> <br/> <p>In general, the decidability and complexity of this problem for two-dimensional matrix semigroups remains open. Recently there was a significant progress with this open problem by showing that the membership is decidable for 2 × 2 nonsingular integer matrices. In this paper we focus on the membership for singular integer matrices and prove that this problem is decidable for 2×2 integer matrices whose determinants are equal to 0, 1, −1 (i.e. for matrices from GL(2,Z) and any singular matrices). Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words and conversion of the membership problem into decision problem on regular languages.</p> |
| first_indexed | 2024-03-07T05:42:10Z |
| format | Conference item |
| id | oxford-uuid:e5f15803-c869-43fb-b7c3-0bd53a72a1d2 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:42:10Z |
| publishDate | 2017 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:e5f15803-c869-43fb-b7c3-0bd53a72a1d22022-03-27T10:27:41ZMembership problem in GL(2, Z) extended by singular matricesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e5f15803-c869-43fb-b7c3-0bd53a72a1d2Symplectic Elements at OxfordSchloss Dagstuhl2017Potapov, ISemukhin, P<p>We consider the membership problem for matrix semigroups, which is the problem to decide whether a matrix belongs to a given finitely generated matrix semigroup.</p> <br/> <p>In general, the decidability and complexity of this problem for two-dimensional matrix semigroups remains open. Recently there was a significant progress with this open problem by showing that the membership is decidable for 2 × 2 nonsingular integer matrices. In this paper we focus on the membership for singular integer matrices and prove that this problem is decidable for 2×2 integer matrices whose determinants are equal to 0, 1, −1 (i.e. for matrices from GL(2,Z) and any singular matrices). Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words and conversion of the membership problem into decision problem on regular languages.</p> |
| spellingShingle | Potapov, I Semukhin, P Membership problem in GL(2, Z) extended by singular matrices |
| title | Membership problem in GL(2, Z) extended by singular matrices |
| title_full | Membership problem in GL(2, Z) extended by singular matrices |
| title_fullStr | Membership problem in GL(2, Z) extended by singular matrices |
| title_full_unstemmed | Membership problem in GL(2, Z) extended by singular matrices |
| title_short | Membership problem in GL(2, Z) extended by singular matrices |
| title_sort | membership problem in gl 2 z extended by singular matrices |
| work_keys_str_mv | AT potapovi membershipproblemingl2zextendedbysingularmatrices AT semukhinp membershipproblemingl2zextendedbysingularmatrices |