Exponential lower bounds for the number of words of uniform length avoiding a pattern

DOI10.1016/J.IC.2007.02.004zbMath1127.68073OpenAlexW2159509242MaRDI QIDQ2381499

Teow Lim Goh, Jason P. Bell

Publication date: 18 September 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2007.02.004

zbMATH Keywords

pattern avoidancecombinatorics on wordsavoidable patterns

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (15)

Doubled patterns with reversal are 3-avoidable ⋮ Doubled patterns are 3-avoidable ⋮ A short proof that shuffle squares are 7-avoidable ⋮ Strict bounds for pattern avoidance ⋮ Application of entropy compression in pattern avoidance ⋮ Another approach to non-repetitive colorings of graphs of bounded degree ⋮ How far away must forced letters be so that squares are still avoidable? ⋮ Doubled patterns with reversal and square-free doubled patterns ⋮ Lower-bounds on the growth of power-free languages over large alphabets ⋮ Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols ⋮ Repetition avoidance in products of factors ⋮ Grasshopper avoidance of patterns ⋮ Highly nonrepetitive sequences: Winning strategies from the local lemma ⋮ Two-Sided Bounds for the Growth Rates of Power-Free Languages ⋮ Density dichotomy in random words

Uses Software

• NAIVE
• DAVID_IAN
• JODO
• BLANKS
• SYMGJ
• SPGJ
• GJseries
• GJSAW
• GJsqfree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern avoidance: themes and variations
• Polynomial versus exponential growth in repetition-free binary words
• Avoidable patterns in strings of symbols
• Uniformly growing k-th power-free homomorphisms
• Unending chess, symbolic dynamics and a problem in semi-groups
• Open Problems in Pattern Avoidance
• The Goulden—Jackson cluster method: extensions, applications and implementations

This page was built for publication: Exponential lower bounds for the number of words of uniform length avoiding a pattern