scientific article; zbMATH DE number 19775

MaRDI QIDQ3979274zbMATH OpenFDO

Authors Klaus Reinhardt

Publication date 26 June 1992

zbMATH Keywords

alternating context-free grammarsalternating pushdown automatacontext- sensitive grammarsoracle hierarchy with finite transducerspolynomial hierarchy

Mathematics Subject Classification ID

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

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)

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