A Note on Alternating Pushdown Automata with Sublogarithmic Space

Jianliang XU  Katsushi INOUE  Yue WANG  Akira ITO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.4   pp.259-270
Publication Date: 1996/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata,Languages and Theory of Computing
Keyword: 
alternating pushdown automata,  sublogarithmic space complexity,  weakly versus strongly,  

Full Text: PDF(1MB)>>
Buy this Article




Summary: 
This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space, and we also show that weakly sublogarithmic space-bounded one-way nondeterministic Turing machines are incomparable with one-way alternating Turing machines with only universal states using the same space. Furthermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigate a relationship between 'strongly' and 'weakly'.