Sets recognized by n-tape automata
Sets recognized by n-tape automata
复制标题
n-tape 自动机识别的集合
DOI：
10.1016/0021-8693(69)90107-0
复制
发表时间：
1969
影响因子：
0.9
通讯作者：
J.C Shepherdson
中科院分区：
文献类型：
--
作者：
S. Eilenberg;C. C. Elgot;J.C Shepherdson
这里研究的n带自动机与普通的有限自动机具有非常接近的rcscmblancc，因为所有的n带同时运动。这种带作用不同于[4]中的n带自动机的作用，在n带自动机中，带的运动是独立的，并由自动机的状态控制。字母表2上的“n带自动机”的概念产生了Z中n元组单词的“n可识别”集合的概念。后者的概念与[I]中所称的“时尚关系”不谋而合。借助于某种一阶解释理论，引入了Z中n元组词的集合是“n-可定义的”的概念。与定义为固定n的“n-可识别”的概念形成鲜明对比的是，“12-可定义”的概念必须同时为所有11个定义。主要结果断言，在铸件中，Z是有限的，并且包含不止一个lcttcr，这两个概念在外延上是等价的。
The n-tape automata studied here, bear a very close rcscmblancc to ordinary finite automata, since all n-tapes move simultaneously. This kind of tape action differs from that of the n-tape automata of [4], where tape motion is individual and is controlled by the state of the automaton. The notion of “n-tape automaton” over an alphabet 2 gives rise to the notion of “n-recognizable” set of n-tuples of words in Z. This latter notion coincides with what is called “FAD relation” in [I]. By means of a certain first-order interpreted theory, the notion that a set of n-tuples of words in Z is “n-definable” is introduced. In contradistinction to the notion “n-recognixahle,” which is defined for fixed n, the notion “12-definable” must be defined simultaneously for all 11. The main result asserts that in the cast that Z is finite and contains more than one lcttcr, these two notions arc extensionally equivalent.