Ogden property for linear displacement context-free grammars

DOI10.1007/978-3-319-27683-0_26zbMATH Open1474.68167OpenAlexW2397966221MaRDI QIDQ5283441FDOQ5283441

Authors: Alexey Sorokin 

Publication date: 21 July 2017

Published in: Logical Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-27683-0_26

Recommendations

• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• Pumping lemma and Ogden lemma for displacement context-free grammars
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• The copying power of well-nested multiple context-free grammars

zbMATH Keywords

pumping lemmacounterexampleslimit Ogden lemmalinear discontinuous context-free languagesOgden lemma

Mathematics Subject Classification ID

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

Cites Work

• A helpful result for proving inherent ambiguity
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• Pumping lemmas for the control language hierarchy
• Pumping lemma and Ogden lemma for displacement context-free grammars
• Monoid automata for displacement context-free languages
• Normal forms for multiple context-free languages and displacement Lambek grammars

Cited In (3)

• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• Pumping lemma and Ogden lemma for displacement context-free grammars
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy

This page was built for publication: Ogden property for linear displacement context-free grammars

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