Some properties of two-dimensional on-line tessellation acceptors
Some properties of two-dimensional on-line tessellation acceptors
复制标题
二维在线镶嵌接受器的一些性质
DOI：
10.1016/0020-0255(77)90023-8
复制
发表时间：
1977
影响因子：
8.1
通讯作者：
A. Nakamura
中科院分区：
文献类型：
--
作者：
Katsushi Inoue;A. Nakamura
本文的目的是提出一种新型接受器，称为“二维在线镶嵌接受器”（记为“2-ota”），并研究 2-ota 的几个属性。 2-ota 可以被认为是由 Smith 和 Beyer 提出的矩形阵列有界元胞空间的实时模式。首先，检查 2-ota 的几个基本属性（例如，封闭属性）。然后，将 2-ota 的接受能力与 Blum 和 Hewitt 提出的二维有限自动机的接受能力进行比较。主要结果为1.1．非确定性2-ota接受的集合类适当地包含非确定性二维有限自动机接受的集合类；2.2．确定性 2-ota 所接受的集合类与确定性（或非确定性）二维有限自动机所接受的集合类是无法比较的。
The purpose of this paper is to propose a new type acceptor called the “two-dimensional on-line tessellation acceptor” (denoted by “2-ota”) and to examine several properties of the 2-ota. The 2-ota might be considered as a real-time mode of rectangular array bounded cellular space, introduced by Smith and Beyer. First, several fundamental properties (e.g., closure properties) of the 2-ota are examined. Then, the accepting power of the 2-ota is compared with that of the two-dimensional finite automaton, introduced by Blum and Hewitt. The main results are1.1. The class of sets accepted by nondeterministic 2-ota's contains properly that of sets accepted by nondeterministic two-dimensional finite automata;2.2. The class of sets accepted by deterministic 2-ota's is incomparable with that of sets accepted by deterministic (or nondeterministic) two-dimensional finite automata.