An “Interchange Lemma” for Context-Free Languages
From MaRDI portal
Publication:3736917
DOI10.1137/0214031zbMath0601.68051OpenAlexW1985092512WikidataQ125017083 ScholiaQ125017083MaRDI QIDQ3736917
No author found.
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214031
Related Items
On languages satisfying “interchange Lemma” ⋮ On the context-freeness of the set of words containing overlaps ⋮ On the language of primitive words ⋮ The interchange or pump (di)lemmas for context-free languages ⋮ Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ Comparisons of Parikh's condition to other conditions for context-free languages ⋮ Properties of infinite words : Recent results ⋮ Most pseudo-copy languages are not context-free ⋮ Edge-label controlled graph grammars ⋮ Permutations are not context-free: An application of the interchange lemma ⋮ The range of non-linear natural polynomials cannot be context-free ⋮ Detecting leftmost maximal periodicities ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata
