Decidability of the Membership Problem for 2 × 2 integer matrices
Decidability of the Membership Problem for 2 × 2 integer matrices
复制标题
2 × 2 整数矩阵隶属问题的可判定性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
P. Semukhin
中科院分区：
文献类型：
--
作者：
I. Potapov;P. Semukhin
本文的主要结果是2 × 2非奇异整数矩阵隶属性问题的可判定性。也就是说，我们将构造第一个算法，对于任何非奇异的2 × 2整数矩阵M1，…， Mn和M决定M是否属于由{M1，…、锰}。我们的算法依赖于将矩阵上的数值问题转化为单词上的组合问题。利用已知的GL（2, 0）子群的一些代数性质以及各种新的技术和构造，将矩阵方程转化为正则语言交点的空性问题。
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.