A geometric hierarchy beyond context-free languages

DOI10.1016/0304-3975(92)90124-XzbMath0754.68070MaRDI QIDQ1200806

David J. Weir

Publication date: 16 January 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational linguisticslanguage hierarchycontrol grammarslabelled distinguished grammarsprogression of automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

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