On multiple context-free grammars
From MaRDI portal
Publication:1177161
DOI10.1016/0304-3975(91)90374-BzbMath0762.68039OpenAlexW2089385274MaRDI QIDQ1177161
Mamoru Fujii, Hiroyuki Seki, Takashi Matsumura, Tadao Kasami
Publication date: 26 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90374-b
tree adjoining grammarscontext free languagescontext sensitive languageshead grammarsmultiple context free grammar
Related Items (66)
\(O_n\) is an \(n\)-MCFL ⋮ Self-avoiding walks and multiple context-free languages ⋮ Comparing consecutive letter counts in multiple context-free languages ⋮ An Approach to Computing Downward Closures ⋮ Algebraic dynamic programming for multiple context-free grammars ⋮ On the effect of the IO-substitution on the Parikh image of semilinear full AFLs ⋮ A Language Theoretic Approach to Syntactic Structure ⋮ Disentangling Notions of Specifier Impenetrability: Late Adjunction, Islands, and Expressive Power ⋮ Topological Classification of RNA Structures via Intersection Graph ⋮ Normal Forms for Multiple Context-Free Languages and Displacement Lambek Grammars ⋮ The word problem of \(\mathbb{Z}^n\) is a multiple context-free language ⋮ Hybrid tree automata and the yield theorem for constituent tree automata ⋮ Non-closure under complementation for unambiguous linear grammars ⋮ A General Technique to Train Language Models on Language Models ⋮ Pumping lemmas for classes of languages generated by folding systems ⋮ Efficiency in the Identification in the Limit Learning Paradigm ⋮ Distributional Learning of Context-Free and Multiple Context-Free Grammars ⋮ Efficient learning of multiple context-free languages with multidimensional substitutability from positive data ⋮ Linear-space recognition for grammars with contexts ⋮ The Cooper storage idiom ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Independent parallelism in finite copying parallel rewriting systems ⋮ Distributional learning of parallel multiple context-free grammars ⋮ Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey ⋮ LR parsing for LCFRS ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ A Note on Multidimensional Dyck Languages ⋮ Extended Lambek Calculi and First-Order Linear Logic ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Abstract Families of Abstract Categorial Languages ⋮ The failure of the strong pumping lemma for multiple context-free languages ⋮ Geometric representations for minimalist grammars ⋮ Observations on Strict Derivational Minimalism ⋮ The Hardest Language for Conjunctive Grammars ⋮ Second-order abstract categorial grammars as hyperedge replacement grammars ⋮ On the membership problem for non-linear abstract categorial grammars ⋮ Global index grammars and descriptive power ⋮ On the expressive power of abstract categorial grammars: Representing context-free formalisms ⋮ Hybrid tree automata and the yield theorem for constituent tree automata ⋮ Unnamed Item ⋮ Ogden's lemma, multiple context-free grammars, and the control language hierarchy ⋮ Translating between Language and Logic: What Is Easy and What Is Difficult ⋮ A grammatical approach to RNA-RNA interaction prediction ⋮ Weighted parsing for grammar-based language models over multioperator monoids ⋮ An Automata Characterisation for Multiple Context-Free Languages ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Closure properties in the class of multiple context-free groups ⋮ Trading independent for synchronized parallelism in finite copying parallel rewriting systems ⋮ The Pumping Lemma for Well-Nested Multiple Context-Free Languages ⋮ Learning Mildly Context-Sensitive Languages with Multidimensional Substitutability from Positive Data ⋮ Groups whose word problems are not semilinear ⋮ On the Mild Context-Sensitivity of k-Tree Wrapping Grammar ⋮ Extended multi bottom-up tree transducers ⋮ Grouped partial ET0L systems and parallel multiple context-free grammars ⋮ IDL-PMCFG, a grammar formalism for describing free word order languages ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ Categorial dependency grammars ⋮ Improved normal form for grammars with one-sided contexts ⋮ MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies ⋮ Synchronous context-free grammars and optimal linear parsing strategies ⋮ Two-sided context specifications in formal grammars ⋮ An operational and denotational approach to non-context-freeness ⋮ Structural similarity within and among languages
Cites Work
This page was built for publication: On multiple context-free grammars
