The equivalence of four extensions of context-free grammars

DOI10.1007/BF01191624zbMath0813.68129MaRDI QIDQ4311636

David J. Weir, K. Vijay-Shanker

Publication date: 30 October 1994

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

context-free grammarscomputational linguists

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Natural language processing (68T50)

Related Items

A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments. ⋮ The grammar of mammalian brain capacity ⋮ Linearity and nondeletion on monadic context-free tree grammars ⋮ Boolean grammars ⋮ Normal Forms for Multiple Context-Free Languages and Displacement Lambek Grammars ⋮ Pumping lemmas for the control language hierarchy ⋮ Information flow in tabular interpretations for generalized push-down automata ⋮ Combinatory categorial grammars as generators of weighted forests ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ Distributional Learning of Context-Free and Multiple Context-Free Grammars ⋮ Restarting Tree Automata and Linear Context-Free Tree Languages ⋮ On the complexity of 2-monotone restarting automata ⋮ Distributional learning of parallel multiple context-free grammars ⋮ Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey ⋮ Linear time parsers for classes of non context free languages ⋮ Consensual languages and matching finite-state computations ⋮ Commutation-augmented pregroup grammars and mildly context-sensitive languages ⋮ Mildly Context-Sensitive Languages via Buffer Augmented Pregroup Grammars ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ On finite-index indexed grammars and their restrictions ⋮ The tree-generative capacity of combinatory categorial grammars ⋮ Highly constrained unification grammars ⋮ An operational and denotational approach to non-context-freeness ⋮ Structural similarity within and among languages ⋮ Tabular parsing and algebraic transformations

Cites Work

• Unnamed Item
• Linear indexed languages
• A geometric hierarchy beyond context-free languages
• Tree adjunct grammars
• Recognition and parsing of context-free languages in time n3
• Indexed Grammars—An Extension of Context-Free Grammars