A Generalization of Ogden's Lemma

DOI10.1145/322307.322315zbMath0501.68039OpenAlexW2014170700WikidataQ124879737 ScholiaQ124879737MaRDI QIDQ3967068

Christopher Bader, Arnaldo Vieira Moura

Publication date: 1982

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322307.322315

zbMATH Keywords

context-free languagespumping lemmaOgden's lemma

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A pumping lemma for real-time deterministic context-free languages ⋮ Parikh’s Theorem and Descriptional Complexity ⋮ The interchange or pump (di)lemmas for context-free languages ⋮ Comparisons of Parikh's condition to other conditions for context-free languages ⋮ Properties of infinite words : Recent results ⋮ Regular and context-free pattern languages over small alphabets ⋮ A pumping lemma for flip-pushdown languages ⋮ Gaining Power by Input Operations: Finite Automata and Beyond ⋮ UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES ⋮ Unbordered partial words ⋮ Comparisons between some pumping conditions for context-free languages ⋮ On context-free and Szilard languages