Pumping lemmas for the control language hierarchy

DOI10.1007/BF01303055zbMath0827.68064WikidataQ124987748 ScholiaQ124987748MaRDI QIDQ4835863

Michael A. Palis, Sunil M. Shende

Publication date: 8 June 1995

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

zbMATH Keywords

control language hierarchy

Mathematics Subject Classification ID

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

Related Items (8)

Ogden Property for Linear Displacement Context-Free Grammars ⋮ The Generative Power of Probabilistic and Weighted Context-Free Grammars ⋮ A geometric hierarchy beyond context-free languages ⋮ Confusion of memory ⋮ The failure of the strong pumping lemma for multiple context-free languages ⋮ Ogden's lemma, multiple context-free grammars, and the control language hierarchy ⋮ The Pumping Lemma for Well-Nested Multiple Context-Free Languages ⋮ DECISION PROBLEMS ON PATH-CONTROLLED GRAMMARS

Cites Work

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

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