Potapov, Igor and Semukhin, Pavel
(2017)
Decidability of the membership problem for 2 × 2 integer matrices.
In: ACM-SIAM Symposium on Discrete Algorithms, 2017-1-16 - 2017-1-19, Barcelona, Spain.
This is the latest version of this item.
Text
1604.02303v1.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (235kB) |
|
Text
mp_siam.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (456kB) |
Abstract
The main result of this paper is the decidability of the membership problem for 2 × 2 nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular 2 × 2 integer matrices M1, . . . , Mn and M decides whether M belongs to the semigroup generated by {M1, . . . , Mn}. Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words. It also makes use of some algebraic properties of well-known subgroups of GL(2, ℤ) and various new techniques and constructions that help to convert matrix equations into the emptiness problem for intersection of regular languages.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | membership problem, matrix semigroups, decidability, nonsingular |
Depositing User: | Symplectic Admin |
Date Deposited: | 10 Feb 2021 09:34 |
Last Modified: | 16 Dec 2022 06:51 |
DOI: | 10.1137/1.9781611974782.12 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3115386 |
Available Versions of this Item
-
Decidability of the Membership Problem for 2 x 2 integer matrices. (deposited 22 Apr 2016 14:04)
- Decidability of the membership problem for 2 × 2 integer matrices. (deposited 10 Feb 2021 09:34) [Currently Displayed]