Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States

Tsunehiro YOSHINAGA  Katsushi INOUE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.1   pp.61-64
Publication Date: 2001/01/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
alternating Turing machines,  multi-inkdot,  two-way computation,  sublogarithmic space complexity,  

Full Text: PDF(146.2KB)>>
Buy this Article




Summary: 
This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTMk(L(n)) (weak-2UTMk(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTMk+1(log log n) - weak-2UTMk(o(log n)) Ø.