Two-Dimensional Alternating Turing Machines with Only Universal States
Two-Dimensional Alternating Turing Machines with Only Universal States
复制标题
仅具有通用状态的二维交替图灵机
DOI：
10.1016/s0019-9958(82)90572-1
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
H. Taniguchi
中科院分区：
文献类型：
--
作者：
A. Ito;Katsushi Inoue;I. Takanami;H. Taniguchi
研究了二维交错图灵机的几个性质。本文第一部分研究了空间有界和有限叶大小的三维有限叶有界二维交替图灵机所接受的集合类与空间有界三向二维非确定图灵机所接受的集合的有限交的集类之间的关系。本文的第二部分研究了只具有普适状态的二维交替图灵机的接受能力和闭包性质(在布尔运算下)。
Several properties of two-dimensional alternating Turing machines are investigated. The first part of this paper investigates the relationship between the classes of sets accepted by space-bounded and finitely leaf-size bounded three-way two-dimensional alternating Turing machines and the classes of sets which are finite intersections of sets accepted by space-bounded three-way two-dimensional nondeterministic Turing machines. The second part of this paper investigates the accepting power and closure properties (under Boolean operations) of two-dimensional alternating Turing machines with only universal states.