Three-way two-dimensional finite automata with rotated inputs
Three-way two-dimensional finite automata with rotated inputs
复制标题
具有旋转输入的三路二维有限自动机
DOI：
10.1016/0020-0255(86)90026-5
复制
发表时间：
1986
影响因子：
8.1
通讯作者：
R. Vollmar
中科院分区：
文献类型：
--
作者：
Katsushi Inoue;I. Takanami;R. Vollmar
本文介绍了一种新的二维自动机--带旋转输入的三路二维有限自动机，并研究了这种新的自动机、二维有限自动机和带界三路二维图灵机的接受能力之间的关系.我们表明，例如，thatmlogmspace（m2空间）是必要的和充分的确定性的三路二维图灵机模拟确定性（非确定性）的三路二维有限自动机旋转输入。
This paper introduces a new type of two-dimensional automaton called a three-way two-dimensional finite automaton with rotated inputs, and investigates a relationship among the accepting powers of these new automata, two-dimensional finite automata, and tape-bounded three-way two-dimensional Turing machines. We show, for example, thatmlogmspace (m2space) is necessary and sufficient for deterministic three-way two-dimensional Turing machines to simulate deterministic (nondeterministic) three-way two-dimensional finite automata with rotated inputs.