Back to Search Start Over

Three-dimensional alternating Turing machines with only universal states

Authors :
Katsushi Inoue
Makoto Sakamoto
Source :
Information Sciences. 95:155-190
Publication Year :
1996
Publisher :
Elsevier BV, 1996.

Abstract

We investigate several properties of three-dimensional alternating Turing machines whose input tapes are restricted to cubic ones. We first investigate the relationship between the classes of sets accepted by space-bounded and finitely leaf-size bounded five-way three-dimensional alternating Turing machines and the classes of sets which are finite intersections of sets accepted by space-bounded five-way three-dimensional nondeterministic Turing machines. Then, we investigate the accepting powers of three-dimensional alternating Turing machines with only universal states.

Details

ISSN :
00200255
Volume :
95
Database :
OpenAIRE
Journal :
Information Sciences
Accession number :
edsair.doi...........2e48e751c6981661f29be5812b8ab5d7
Full Text :
https://doi.org/10.1016/s0020-0255(96)00124-7