The Effect of Inkdots for Two-Dimensional Automata
The Effect of Inkdots for Two-Dimensional Automata
复制标题
墨点对二维自动机的影响
DOI：
10.1142/s0218001495000328
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Yue Wang
中科院分区：
文献类型：
--
作者：
A. Ito;Katsushi Inoue;I. Takanami;Yue Wang
最近，关于确定性和非确定性空间（特别是低级别）复杂性类是否分离的公开问题，引入了墨水点图灵机。墨点机是一个传统的图灵机能够下降的墨点在一个给定的输入磁带上的地标，但不拿起它，也不进一步erase it.In本文中，我们介绍了一个有限状态版本的墨点机作为一个弱识别器的数字图片的属性，而不是图灵机提供了一个一维的工作磁带。我们首先研究了三路图灵机模拟二维墨水点有限自动机的充分空间，作为初步结果。其次，我们研究了二维墨水点自动机的基本性质，即基于墨水点数量的层次结构以及二维墨水点自动机与其他常规二维自动机的关系。最后，我们研究了二维墨水点有限机器的连通图的可识别性。
Recently, related to the open problem of whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, the inkdot Turing machine was introduced. An inkdot machine is a conventional Turing machine capable of dropping an inkdot on a given input tape for a landmark, but not to pick it up nor further erase it. In this paper, we introduce a finite state version of the inkdot machine as a weak recognizer of the properties of digital pictures, rather than a Turing machine supplied with a one-dimensional working tape. We first investigate the sufficient spaces of three-way Turing machines to simulate two-dimensional inkdot finite automaton, as preliminary results. Next, we investigate the basic properties of two-dimensional inkdot automaton, i.e. the hierarchy based on the number of inkdots and the relationship of two-dimensional inkdot automata to other conventional two-dimensional automata. Finally, we investigate the recognizability of connected pictures of two-dimensional inkdot finite machines.