A Note on Two-Dimensional Probabilistic Turing Machines
A Note on Two-Dimensional Probabilistic Turing Machines
复制标题
关于二维概率图灵机的注解
DOI：
10.1016/s0020-0255(98)10049-x
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Yue Wang
中科院分区：
文献类型：
--
作者：
T. Okazaki;Katsushi Inoue;A. Ito;Yue Wang
本文介绍了二维概率图灵机（2-ptm），并研究了它的一些性质。本文首先研究了错误概率小于1 2的二维交替有限自动机（2-afa）与具有次对数空间的2-ptm之间的关系，证明了存在一组被2-afa接受，但不被任何错误概率小于1 2的o（log-n）空间有界的2-ptm识别的方带.这部分解决了Okazaki等人（Inform.科学，出现）。其次，我们研究了具有次对数空间且错误概率小于1 2的2-ptm的空间层次，并证明了如果L（n）是二维图灵机的空间可构造的，则存在一组由强L（n）空间有界的二维确定图灵机接受的方带，但不被任何L（n）空间有界的2-ptm识别，错误概率小于1 2。
This paper introduces two-dimensional probabilistic Turing machines (2-ptm's), and investigates several properties of them. We first investigate a relationship between two-dimensional alternating finite automata (2-afa's) and 2-ptm's with error probability less than 1 2 and with sublogarithmic space, and show that there is a set of square tapes accepted by 2-afa, but not recognized by any o(log-n) space-bounded 2-ptm with error probability less than 1 2 . This partially solves an open problem in Okazaki et al. (Inform. Sci., to appear). We next investigate a space hierarchy of 2-ptm's with error probability less than 1 2 and with sublogarithmic space, and show that if L(n) is space-constructible by a two-dimensional Turing machine, there is a set of square tapes accepted by a strongly L(n) space-bounded two-dimensional deterministic Turing machine, but not recognized by any L(n) space-bounded 2-ptm with error probability less than 1 2 .