Shrinking Alternating Two-Pushdown Automata

Friedrich OTTO  Etsuro MORIYA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.4   pp.959-966
Publication Date: 2004/04/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata and Formal Language Theory
Keyword: 
shrinking,  alternating,  two-pushdown automaton,  PSPACE-complete,  

Full Text: PDF>>
Buy this Article



Summary: 
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.