Decidability of the Membership Problem for $2\times 2$ integer matrices

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.

No reviews yet.

No comments yet.