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.
Shrinking Alternating Two-Pushdown Automata
Friedrich OTTO Etsuro MORIYA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/04/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata and Formal Language Theory
shrinking, alternating, two-pushdown automaton, PSPACE-complete,
Full Text: PDF>>
The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.