scientific article; zbMATH DE number 4050986

MaRDI QIDQ3787475zbMATH OpenFDO

Authors Birgit Jenner, Bernd Kirsig

Publication date 1988

zbMATH Keywords

alternating auxiliary pushdown hierarchycomplexity theorylogarithmic alternation hierarchymachine modelPSPACEpushdown automata with unbounded alternationpushdown store

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Alternation bounded auxiliary pushdown automata
• scientific article; zbMATH DE number 19775
• Alternation for sublogarithmic space-bounded alternating pushdown automata
• scientific article; zbMATH DE number 1759428
• Alternating and empty alternating auxiliary stack automata.

Cited in

(9)

• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
• A grammatical characterization of alternating pushdown automata
• Alternating and empty alternating auxiliary stack automata.
• scientific article; zbMATH DE number 4131657 (Why is no real title available?)
• Alternation bounded auxiliary pushdown automata
• scientific article; zbMATH DE number 19775 (Why is no real title available?)
• Reversals and alternation
• Predicate characterizations in the polynomial-size hierarchy
• Logspace verifiers, NC, and NP

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787475)