Permutations are not context-free: An application of the interchange lemma

DOI10.1016/0020-0190(82)90109-0zbMath0486.68077OpenAlexW1988548256WikidataQ124817934 ScholiaQ124817934MaRDI QIDQ1165021

Michael G. Main

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90109-0

zbMATH Keywords

permutationscontext-free languagesrepetitionspermutation-containing string

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Applications of an infinite square-free co-CFL ⋮ The interchange or pump (di)lemmas for context-free languages ⋮ An infinite square-free co-CFL

Cites Work

• Avoidable patterns in strings of symbols
• An “Interchange Lemma” for Context-Free Languages
• On Context-Free Languages
• A helpful result for proving inherent ambiguity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item