A geometric hierarchy beyond context-free languages
From MaRDI portal
Publication:1200806
DOI10.1016/0304-3975(92)90124-XzbMath0754.68070MaRDI QIDQ1200806
Publication date: 16 January 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
computational linguisticslanguage hierarchycontrol grammarslabelled distinguished grammarsprogression of automata
Related Items (18)
The grammar of mammalian brain capacity ⋮ Cooperating Distributed Tree Automata ⋮ Pumping lemmas for the control language hierarchy ⋮ The equivalence of four extensions of context-free grammars ⋮ Unnamed Item ⋮ A finite state intersection approach to propositional satisfiability ⋮ A survey of recent[1985-1995advances in generalized convexity with applications to duality theory and optimality conditions] ⋮ Linear time parsers for classes of non context free languages ⋮ Storage products and linear control of derivations ⋮ Confusion of memory ⋮ The failure of the strong pumping lemma for multiple context-free languages ⋮ Global index grammars and descriptive power ⋮ Ogden's lemma, multiple context-free grammars, and the control language hierarchy ⋮ Two complementary operations inspired by the DNA hairpin formation: Completion and reduction ⋮ Highly constrained unification grammars ⋮ DECISION PROBLEMS ON PATH-CONTROLLED GRAMMARS ⋮ Even linear simple matrix languages: formal language properties and grammatical inference. ⋮ wMSO theories as grammar formalisms
Cites Work
- Linear indexed languages
- Upper bounds on recognition of a hierarchy of non-context-free languages
- A geometric hierarchy of languages
- Tree adjunct grammars
- Pushdown tree automata
- Iterated linear control and iterated one-turn pushdowns
- The complexity of the membership problem for some extensions of context-free languagest†
- Pumping lemmas for the control language hierarchy
- Indexed Grammars—An Extension of Context-Free Grammars
This page was built for publication: A geometric hierarchy beyond context-free languages
