Membership Problem in GL(2, Z) Extended by Singular Matrices
Membership Problem in GL(2, Z) Extended by Singular Matrices
复制标题
奇异矩阵扩展的 GL(2, Z) 中的隶属度问题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Semukhin
中科院分区：
文献类型：
--
作者：
I. Potapov;P. Semukhin
© 伊戈尔·波塔波夫和帕维尔·塞穆欣；根据知识共享许可 CC-BY 获得许可。我们考虑矩阵半群的隶属度问题，即决定一个矩阵是否属于给定的有限生成矩阵半群的问题。一般来说，二维矩阵半群这个问题的可判定性和复杂性仍然是开放的。最近，这个开放问题取得了重大进展，表明 2 X 2 非奇异整数矩阵的成员资格是可判定的。在本文中，我们关注奇异整数矩阵的隶属度，并证明该问题对于行列式等于 0、1、-1 的 2X2 整数矩阵（即来自 GL(2,Z) 的矩阵和任何奇异矩阵）是可判定的。我们的算法依赖于将矩阵上的数值问题转换为单词上的组合问题以及将隶属度问题转换为常规语言上的决策问题。
© Igor Potapov and Pavel Semukhin; licensed under Creative Commons License CC-BY. We consider the membership problem for matrix semigroups, which is the problem to decide whether a matrix belongs to a given finitely generated matrix semigroup. In general, the decidability and complexity of this problem for two-dimensional matrix semigroups remains open. Recently there was a significant progress with this open problem by showing that the membership is decidable for 2 X 2 nonsingular integer matrices. In this paper we focus on the membership for singular integer matrices and prove that this problem is decidable for 2X2 integer matrices whose determinants are equal to 0, 1, -1 (i.e. for matrices from GL(2,Z) and any singular matrices). Our algorithm relies on a translation of numerical problems on matrices into combinatorial problems on words and conversion of the membership problem into decision problem on regular languages.