A short proof that shuffle squares are 7-avoidable

DOI10.1051/ita/2016007zbMath1353.68224OpenAlexW2438726950MaRDI QIDQ3186679

Guillaume Guégan, Pascal Ochem

Publication date: 12 August 2016

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e76626ee8f3252b9d6816bf6ee72e0b9030a11a2

zbMATH Keywords

exponential growthformal power seriesentropy compressionavoidanceshuffle square

Mathematics Subject Classification ID

Combinatorics on words (68R15) Entropy in general topology (54C70) Formal power series rings (13F25)

Related Items (4)

Approaching repetition thresholds via local resampling and entropy compression ⋮ On shuffled-square-free words ⋮ Avoiding or Limiting Regularities in Words ⋮ Recognizing binary shuffle squares is \textsf{NP}-hard

Cites Work

• Strict bounds for pattern avoidance
• Application of entropy compression in pattern avoidance
• Further applications of a power series method for pattern avoidance
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• Doubled patterns are 3-avoidable
• New approach to nonrepetitive sequences

This page was built for publication: A short proof that shuffle squares are 7-avoidable