Two-dimensional alternating Turing machines
Two-dimensional alternating Turing machines
复制标题
二维交替图灵机
DOI：
10.1145/800070.802175
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
H. Taniguchi
中科院分区：
文献类型：
--
作者：
Katsushi Inoue;I. Takanami;H. Taniguchi
本文介绍了一种二维交替图灵机（2-ATM），它是交替图灵机在二维上的推广。本文还介绍了三路二维交替图灵机（TR 2-ATM），它是三路二维图灵机的交替版本。我们首先研究了空间有界2-ATM（或TR 2-ATM）和普通空间有界二维图灵机（或三路二维图灵机）的接受能力之间的关系。然后，我们介绍了一个简单的，自然的复杂性措施2-ATM的（或TR 2-ATM的），所谓的-&-ldquo;叶大小-&-rdquo;，并提供了一个频谱的复杂性类的基础上叶大小有界的计算。最后，我们研究了2-ATM（或TR 2-ATM）的连通模式的识别能力。
This paper introduces a two-dimensional alternating Turing machine (2-ATM) which is an extension of an alternating Turing machine to two-dimensions. This paper also introduces a three-way two-dimensional alternating Turing machine (TR2-ATM) which is an alternating version of a three-way two-dimensional Turing machine. We first investigate a relationship between the accepting powers of space-bounded 2-ATM's (or TR2-ATM's) and ordinary space-bounded two-dimensional Turing machines (or three-way two-dimensional Turing machines). We then introduce a simple, natural complexity measure for 2-ATM's (or TR2-ATM's), called -&-ldquo;leaf-size-&-rdquo;, and provides a spectrum of complexity classes based on leaf-size bounded computations. We finally investigate the recognizability of connected patterns by 2-ATM's (or TR2-ATM's).