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.
A Note on Alternating Pushdown Automata with Sublogarithmic Space
Jianliang XU Katsushi INOUE Yue WANG Akira ITO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/04/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata,Languages and Theory of Computing
alternating pushdown automata, sublogarithmic space complexity, weakly versus strongly,
Full Text: PDF(1MB)>>
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'.