scientific article; zbMATH DE number 19775

MaRDI QIDQ3979274zbMATH OpenFDO

Authors Klaus Reinhardt

Publication date 26 June 1992

zbMATH Keywords

polynomial hierarchyalternating pushdown automatacontext- sensitive grammarsalternating context-free grammarsoracle hierarchy with finite transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 4050986
• Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages
• Alternation bounded auxiliary pushdown automata
• A grammatical characterization of alternating pushdown automata
• On state-alternating context-free grammars

Cited in

(12)

• An automata-theoretical characterization of the OI-hierarchy
• An oracle hierarchy for small one-way finite automata
• scientific article; zbMATH DE number 4050986 (Why is no real title available?)
• Predicate characterizations in the polynomial-size hierarchy
• Alternating context-free languages and linear time \(\mu \)-calculus with sequential composition
• A geometric hierarchy beyond context-free languages
• Empty alternation
• Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages
• Alternating Turing machines for inductive languages
• A characterization of exponential-time languages by alternating context- free grammars
• On Alternating Phrase-Structure Grammars
• Alternation for sublogarithmic space-bounded alternating pushdown automata

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 Q3979274)