Shrinking alternating two-pushdown automata

Friedrich Otto*, Etsuro Moriya

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    5 Citations (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)959-966
    Number of pages8
    JournalIEICE Transactions on Information and Systems
    Issue number4
    Publication statusPublished - 2004 Apr


    • Alternating
    • PSPACE-complete
    • Shrinking
    • Two-pushdown automaton

    ASJC Scopus subject areas

    • Information Systems
    • Computer Graphics and Computer-Aided Design
    • Software


    Dive into the research topics of 'Shrinking alternating two-pushdown automata'. Together they form a unique fingerprint.

    Cite this