Decidability of the membership problem for 2 × 2 integer matrices



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.

[img] Text
1604.02303v1.pdf - Author Accepted Manuscript
Available under License : See the attached licence file.

Download (235kB)
[img] 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