Two-dimensional automata with rotated inputs
Two-dimensional automata with rotated inputs
复制标题
具有旋转输入的二维自动机
DOI：
10.1016/0020-0255(80)90032-8
复制
发表时间：
1980
影响因子：
8.1
通讯作者：
H. Taniguchi
中科院分区：
文献类型：
--
作者：
Katsushi Inoue;I. Takanami;H. Taniguchi
本文介绍了一种新型的二维磁带自动机，它通过各种自动机从不同侧面扫描磁带来决定是否接受输入磁带。研究了这种自动机的接受能力。本文主要研究由M1，M2，M3和M4四个并行/顺序阵列自动机组成的二维自动机的接受能力，它们接受一个输入带xif，且只有x，xR，（xR）R和（（xR）R）Rare分别被M1，M2，M3和M4接受，其中对任意带，yR是顺时针旋转90°得到的带.
This paper introduces a new type of automata on a two-dimensional tape, which decides acceptance or rejection of an input tapexby scanning the tapexfrom various sides by various automata. The accepting power of such an automaton is investigated. This paper mainly concentrates on investigating the accepting power of two-dimensional automata which consist of four parallel/sequential array automata, sayM1,M2,M3, andM4, and which accept an input tapexif and only ifx,xR, (xR)R, and ((xR)R)Rare accepted byM1,M2,M3, andM4, respectively, where for any tapey,yRis the tape obtained by rotatingyclockwise 90°.