Ogden's Lemma for Regular Tree Languages

2008/10/23 by Kuhlmann, Marco
#Computational Complexity (cs.CC) #F.4.3 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0810.4249

Abstract

We motivate and prove a strong pumping lemma for regular tree languages. The new lemma can be seen as the natural correspondent of Ogden's lemma for context-free string languages.

Related

• Pumping lemma and Ogden lemma for displacement context-free grammars
• A short survey around the pumping lemma for context-free languages
• Pumping Lemma for Higher-order Languages
• A Proof of the Pumping Lemma for Context-Free Languages Through Pushdown Automata
• Formalization of the pumping lemma for context-free languages