Improved matrix pair undecidability results
Improved matrix pair undecidability results
复制标题
改进的矩阵对不可判定性结果
DOI：
10.1007/s00236-007-0047-y
复制
发表时间：
2007
期刊：
影响因子：
0.6
通讯作者：
M. Hirvensalo
中科院分区：
文献类型：
--
作者：
Vesa Halava;M. Hirvensalo
我们改进了涉及两个整数矩阵的问题的不可判定性界限，表明标量可达性，零右上角，向量可达性，零左上角分别为9，10，11和13维不可判定。标量可达性、右上角零和向量可达性问题以前分别被认为是18、18和16维的不可判定问题。
We improve the undecidability bounds for problems involving two integer matrices by showing that Scalar Reachability, Zero in the Right Upper Corner, Vector Reachability, and Zero in the Left Upper Corner are undecidable for dimensions of 9, 10, 11, and 13, respectively. Problems Scalar Reachability, Zero in the Right Upper Corner, and Vector Reachability were previously known undecidable for dimensions 18, 18, and 16, respectively.