Some Results Concerning Two-Dimensional Turing Machines and Finite Automata
Some Results Concerning Two-Dimensional Turing Machines and Finite Automata
复制标题
有关二维图灵机和有限自动机的一些结果
DOI：
10.1007/3-540-60249-6_69
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
H. Petersen
中科院分区：
文献类型：
--
作者：
H. Petersen
我们表明，空性是可判定的三维二维非确定性有限自动机以及宇宙问题的相应类的确定性自动机。对于单字母表上的三路（甚至两路）二维交替有限自动机，空性是不可判定的。因此，包含，等价，和不相交的这些自动机是不可判定的properties.We建立了一个层次结构的结果，空间有界的二维交替图灵机以上对数的语言见证层次结构是在单字母表。在对数以下，我们证明了在较大的字母表上存在一个无限的语言层次结构。结果主要依赖于从一维到二维的翻译技术。使用这种技术，我们还可以显示二维自动机理论和一维复杂性理论的开放问题之间的一些联系。
We show that emptiness is decidable for three-way two-dimensional nondeterministic finite automata as well as the universe problem for the corresponding class of deterministic automata. Emptiness is undecidable for three-way (and even two-way) two-dimensional alternating finite automata over a single-letter alphabet. Consequently inclusion, equivalence, and disjointness for these automata are undecidable properties.We establish a hierarchy result for space bounded two-dimensional alternating Turing machines above logarithm where the languages witnessing the hierarchy are over single-letter alphabets. Below logarithm we prove that an infinite hierarchy of languages over larger alphabets exists.The results rely mainly on a translational technique from one to two dimensions. Using this technique we can also show some connections between open problems of two-dimensional automata theory and one-dimensional complexity theory.