Vector Reachability Problem in SL(2, Z)
Vector Reachability Problem in SL(2, Z)
复制标题
SL(2, Z) 中的向量可达性问题
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
P. Semukhin
中科院分区：
文献类型：
--
作者：
I. Potapov;P. Semukhin
几十年来，由于矩阵乘积在各种计算过程的表示中起着重要的作用，对矩阵的决策问题进行了深入的研究。然而，矩阵半群的许多计算问题即使对于低维问题也是难于解决的，而且大多数矩阵半群问题一般从三维或四维开始就变得不可判定。
本文解决了关于SL(2，Z)的有限生成矩阵半群上的向量可达性问题和分式线性变换的点对点可达性(在有理数上)的两个公开问题，其中相关矩阵来自SL(2，Z)。求解可达性问题的方法是基于点与点之间的可达性路径的刻画，然后将矩阵上的数值问题转化为词和形式语言上的计算和组合问题。我们还给出了可达路的几何解释，并将可判定性结果推广到由任意标号有向图表示的矩阵乘积。最后，我们将使用这个技巧来证明标量可达性问题的一个特例是可判定的。
The decision problems on matrices were intensively studied for many decades as matrix products play an essential role in the representation of various computational processes. However, many computational problems for matrix semigroups are inherently difficult to solve even for problems in low dimensions and most matrix semigroup problems become undecidable in general starting from dimension three or four.
This paper solves two open problems about the decidability of the vector reachability problem over a finitely generated semigroup of matrices from SL(2, Z) and the point to point reachability (over rational numbers) for fractional linear transformations, where associated matrices are from SL(2, Z). The approach to solving reachability problems is based on the characterization of reachability paths between points which is followed by the translation of numerical problems on matrices into computational and combinatorial problems on words and formal languages. We also give a geometric interpretation of reachability paths and extend the decidability results to matrix products represented by arbitrary labelled directed graphs. Finally, we will use this technique to prove that a special case of the scalar reachability problem is decidable.