For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States
Tsunehiro YOSHINAGA Jianliang XU Katsushi INOUE
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
multi-inkdot Turing machines, alternating Turing machines, sublogarithmic space complexity, complementation,
Full Text: PDF(94.3KB)>>
This paper investigates the accepting powers of two-way alternating Turing machines (2ATM's) with only existential (universal) states which have inkdots and sublogarithmic space. It is shown that for sublogarithmic space-bounded computations, (i) multi-inkdot 2ATM's with only existential states and the ones with only universal states are incomparable, (ii) k-inkdot 2ATM's are better than k-inkdot 2ATM's with only existential (universal) states, k ≥ 0, and (iii) the class of sets accepted by multi-inkdot 2ATM's with only existential (universal) states is not closed under complementation.