scientific article; zbMATH DE number 19775
From MaRDI portal
Publication:3979274
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
polynomial hierarchyalternating pushdown automatacontext- sensitive grammarsalternating context-free grammarsoracle hierarchy with finite transducers
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)