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 linguistics; language hierarchy; control grammars; labelled distinguished grammars; progression of automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

The equivalence of four extensions of context-free grammars, A survey of recent[1985-1995advances in generalized convexity with applications to duality theory and optimality conditions], Pumping lemmas for the control language hierarchy, A finite state intersection approach to propositional satisfiability, Linear time parsers for classes of non context free languages, Confusion of memory, Two complementary operations inspired by the DNA hairpin formation: Completion and reduction, Highly constrained unification grammars, Global index grammars and descriptive power, Even linear simple matrix languages: formal language properties and grammatical inference., wMSO theories as grammar formalisms, Storage products and linear control of derivations, Cooperating Distributed Tree Automata, DECISION PROBLEMS ON PATH-CONTROLLED GRAMMARS

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