Potapov, Igor and Semukhin, Pavel
(2016)
Decidability of the Membership Problem for $2\times 2$ integer matrices.
[Preprint]
|
Text
1604.02303v1.pdf - Author Accepted Manuscript Download (240kB) | Preview |
Abstract
The main result of this paper is the decidability of the membership problem for $2\times 2$ nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular $2\times 2$ integer matrices $M_1,\dots,M_n$ and $M$ decides whether $M$ belongs to the semigroup generated by $\{M_1,\dots,M_n\}$. Our algorithm relies on a translation of the numerical problem on matrices into combinatorial problems on words. It also makes use of some algebraical properties of well-known subgroups of $\mathrm{GL}(2,\mathbb{Z})$ and various new techniques and constructions that help to limit an infinite number of possibilities by reducing them to the membership problem for regular languages.
| Item Type: | Preprint |
|---|---|
| Uncontrolled Keywords: | cs.DM, cs.DM, cs.FL, F.2.1; F.1.1 |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 25 Jul 2022 15:28 |
| Last Modified: | 15 Mar 2024 07:12 |
| DOI: | 10.48550/arxiv.1604.02303 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3159481 |
Dimensions
Dimensions
