Pumping lemmas for the control language hierarchy

DOI10.1007/BF01303055zbMATH Open0827.68064WikidataQ124987748 ScholiaQ124987748MaRDI QIDQ4835863FDOQ4835863

Authors: Michael A. Palis, Sunil Shende 

Publication date: 8 June 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Recommendations

• Pumping lemmas for linear and nonlinear context-free languages
• Pumping lemmas for special linear languages
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• A geometric hierarchy beyond context-free languages

zbMATH Keywords

control language hierarchy

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A geometric hierarchy beyond context-free languages
• Tree adjunct grammars
• The equivalence of four extensions of context-free grammars
• Indexed Grammars—An Extension of Context-Free Grammars
• Upper bounds on recognition of a hierarchy of non-context-free languages
• Title not available (Why is that?)
• Simple matrix languages
• A hierarchy between context-free and context-sensitive languages
• Matrix grammars with a leftmost restriction
• A geometric hierarchy of languages
• Control sets on grammars
• Programmed Grammars and Classes of Formal Languages
• Title not available (Why is that?)

Cited In (10)

• Title not available (Why is that?)
• The generative power of probabilistic and weighted context-free grammars
• The failure of the strong pumping lemma for multiple context-free languages
• Decision problems on path-controlled grammars
• A geometric hierarchy beyond context-free languages
• Ogden property for linear displacement context-free grammars
• Pumping Lemma for Higher-order Languages
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• Confusion of memory

This page was built for publication: Pumping lemmas for the control language hierarchy

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