The Pumping Lemma for Well-Nested Multiple Context-Free Languages

DOI10.1007/978-3-642-02737-6_25MaRDI QIDQ3637235zbMATH OpenOpenAlexFDO

Authors Makoto Kanazawa

Publication date 7 July 2009

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02737-6_25

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The copying power of well-nested multiple context-free grammars
• The failure of the strong pumping lemma for multiple context-free languages
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• Pumping lemmas for linear and nonlinear context-free languages
• A pumping lemma for deterministic context-free languages

Cites work

• Closure properties of linear context-free tree languages with an application to optimality theory
• scientific article; zbMATH DE number 1104368 (Why is no real title available?)
• Independent parallelism in finite copying parallel rewriting systems
• On multiple context-free grammars
• On parsing coupled-context-free languages
• Pumping lemmas for the control language hierarchy
• The mathematics of language
• The string generating power of context-free hypergraph grammars
• Theory of Formal Systems. (AM-47)

Cited in

(20)

• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language
• The Cooper storage idiom
• Multiple context-free tree grammars: lexicalization and characterization
• The failure of the strong pumping lemma for multiple context-free languages
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• On the Mild Context-Sensitivity of k-Tree Wrapping Grammar
• A pumping lemma for collapsible pushdown graphs of level 2
• Pumping lemmas for linear and nonlinear context-free languages
• Disentangling notions of specifier impenetrability: late adjunction, islands, and expressive power
• Normal forms for multiple context-free languages and displacement Lambek grammars
• The copying power of well-nested multiple context-free grammars
• scientific article; zbMATH DE number 1222097 (Why is no real title available?)
• scientific article; zbMATH DE number 522860 (Why is no real title available?)
• Pumping Lemma for Higher-order Languages
• Ogden property for linear displacement context-free grammars
• Extended Lambek calculi and first-order linear logic
• Pumping lemmas for classes of languages generated by folding systems
• Comparing consecutive letter counts in multiple context-free languages

This page was built for publication: The Pumping Lemma for Well-Nested Multiple Context-Free Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637235)