Ogden property for linear displacement context-free grammars

DOI10.1007/978-3-319-27683-0_26MaRDI QIDQ5283441zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)