Ogden's lemma, multiple context-free grammars, and the control language hierarchy

DOI10.1016/j.ic.2019.104449zbMath1435.68172OpenAlexW2970221579WikidataQ124866797 ScholiaQ124866797MaRDI QIDQ2280330

Makoto Kanazawa

Publication date: 18 December 2019

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2019.104449

zbMATH Keywords

grammarspumping lemmamultiple context-free grammarscontrol languagesOgden's lemma

Mathematics Subject Classification ID

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

Related Items (1)

Special issue: selected papers of the 10th international conference on language and automata theory and applications, LATA 2016

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On multiple context-free grammars
• A geometric hierarchy beyond context-free languages
• One way finite visit automata
• Hierarchy theorems for two-way finite state transducers
• The failure of the strong pumping lemma for multiple context-free languages
• AFL with the semilinear property
• Pumping Lemma and Ogden Lemma for Displacement Context-Free Grammars
• The Copying Power of Well-Nested Multiple Context-Free Grammars
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• Pumping lemmas for the control language hierarchy
• Ogden Property for Linear Displacement Context-Free Grammars
• A helpful result for proving inherent ambiguity
• Full AFLs and nested iterated substitution
• A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free

This page was built for publication: Ogden's lemma, multiple context-free grammars, and the control language hierarchy