scientific article; zbMATH DE number 19775

zbMATH Open0735.68052MaRDI QIDQ3979274FDOQ3979274

Authors: Klaus Reinhardt 

Publication date: 26 June 1992

Title of this publication is not available (Why is that?)

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

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)

Cited In (12)

• Title not available (Why is that?)
• Predicate characterizations in the polynomial-size hierarchy
• An automata-theoretical characterization of the OI-hierarchy
• A characterization of exponential-time languages by alternating context- free grammars
• Alternating Turing machines for inductive languages
• A geometric hierarchy beyond context-free languages
• Alternating context-free languages and linear time \(\mu \)-calculus with sequential composition
• An oracle hierarchy for small one-way finite automata
• Empty alternation
• Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages
• 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)