Exponential lower bounds for the number of words of uniform length avoiding a pattern
From MaRDI portal
Publication:2381499
DOI10.1016/j.ic.2007.02.004zbMath1127.68073OpenAlexW2159509242MaRDI QIDQ2381499
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
Related Items (14)
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 ⋮ 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
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
