Some Observations on One-way Alternating Pushdown Automata with Sublinear Space

Jianliang XU  Tsunehiro YOSHINAGA  Katsushi INOUE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.5   pp.1012-1019
Publication Date: 2004/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
alternating pushdown automata,  sublogarithmic complexity,  sublinear complexity,  space hierarchy,  

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

This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.