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...
| Հիմնական հեղինակներ: | , |
|---|---|
| Ձևաչափ: | Conference item |
| Հրապարակվել է: |
Schloss Dagstuhl
2017
|
| Ամփոփում: | <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> |
|---|