Reachability problems in low-dimensional nondeterministic polynomial maps over integers
Reachability problems in low-dimensional nondeterministic polynomial maps over integers
复制标题
整数上的低维非确定性多项式映射的可达性问题
DOI：
10.1016/j.ic.2021.104785
复制
发表时间：
2021
影响因子：
1
通讯作者：
Ko S
中科院分区：
文献类型：
--
作者：
Ko S
我们研究了Z n中各种非确定多项式映射的可达性问题。我们证明了非常简单的三维仿射映射（独立变量）的可达性问题是不可判定的，是PSPACE困难的二维仿射映射和一维二次映射。然后我们证明了不含形式为±x+ a 0的函数的映射的可达性问题的复杂性较低。在这种情况下，可达性问题对于任何维度都是PSPACE，如果维度不固定，则问题是PSPACE完全的。最后，我们扩展了模型，考虑地图作为语言受体，并证明了普遍性问题是不可判定的二维仿射映射。
We study reachability problems for various nondeterministic polynomial maps in Z n. We prove that the reachability problem for very simple three-dimensional affine maps (with independent variables) is undecidable and is PSPACE-hard for both two-dimensional affine maps and one-dimensional quadratic maps. Then we show that the complexity of the reachability problem for maps without functions of the form±x+ a 0 is lower. In this case the reachability problem is PSPACE for any dimension and if the dimension is not fixed, then the problem is PSPACE-complete. Finally we extend the model by considering maps as language acceptors and prove that the universality problem is undecidable for two-dimensional affine maps.
登录
查看更多内容
矩阵半群的不变性问题
影响因子：
8
作者：
Klaus Dräger
通讯作者：
Klaus Dräger
目标贴现总和问题
DOI：
10.1109/lics.2015.74
发表时间：
2015
期刊：
2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Udi Boker;T. Henzinger;J. Otop
通讯作者：
J. Otop
DOI：
10.46298/lmcs-17(3:1)2021
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Michael Blondin;C. Haase;Filip Mazowiecki
通讯作者：
Filip Mazowiecki
改进的矩阵对不可判定性结果
影响因子：
0.6
作者：
Vesa Halava;M. Hirvensalo
通讯作者：
M. Hirvensalo
GL(2, Q) 和奇异矩阵的平有理子集隶属问题的可判定性
DOI：
10.1145/3373207.3404038
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Diekert V
通讯作者：
Diekert V