Decidability of the membership problem for 2 × 2 integer matrices

Igor Potapov, Pavel Semukhin

Symposium on Discrete Algorithms · 2017 · 15 citations · 15 references

Concepts

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.

References

15