Polynomial versus exponential growth in repetition-free binary words

DOI10.1016/j.jcta.2003.12.004zbMath1065.68080arXivmath/0304095OpenAlexW2084593271MaRDI QIDQ598459

Juhani Karhumäki, Jeffrey O. Shallit

Publication date: 6 August 2004

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0304095

zbMATH Keywords

CubefreeExponential growthFractional powerPolynomial growthRepetition-free

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (32)

The critical exponent functions ⋮ Overlap-free words and spectra of matrices ⋮ Letter frequency in infinite repetition-free words ⋮ On the entropy and letter frequencies of powerfree words ⋮ Exponential lower bounds for the number of words of uniform length avoiding a pattern ⋮ Fewest repetitions in infinite binary words ⋮ Lengths of extremal square-free ternary words. ⋮ Infinite words containing the minimal number of repetitions ⋮ Minimal critical exponent of quasiperiodic words ⋮ Interview with Jeffrey Shallit ⋮ On patterns occurring in binary algebraic numbers ⋮ Deciding context equivalence of binary overlap-free words in linear time ⋮ Avoiding or Limiting Regularities in Words ⋮ Fewest repetitions versus maximal-exponent powers in infinite binary words ⋮ Growth properties of power-free languages ⋮ On Dejean's conjecture over large alphabets ⋮ Relations on words ⋮ Growth of repetition-free words -- a review ⋮ Pattern avoidance: themes and variations ⋮ Avoiding large squares in infinite binary words ⋮ The Number of Threshold Words on $n$ Letters Grows Exponentially for Every $n\geq 27$ ⋮ On the number of \(\alpha \)-power-free binary words for \(2<\alpha \leq 7/3\) ⋮ Infinite words containing squares at every position ⋮ Growth rates of complexity of power-free languages ⋮ On maximal repetitions of arbitrary exponent ⋮ The repetition threshold for binary rich words ⋮ Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices ⋮ Transition property for cube-free words ⋮ Two-Sided Bounds for the Growth Rates of Power-Free Languages ⋮ Growth rates of power-free languages ⋮ Subword complexity and power avoidance ⋮ A generator of morphisms for infinite words

Cites Work

• Repetition-free words
• Enumeration of irreducible binary words
• On repetitions of blocks in binary sequences
• Overlap-free words and finite automata
• On repetition-free binary words of minimal density
• Uniformly growing k-th power-free homomorphisms
• Sur un théorème de Thue
• The structure of the set of cube-free $ Z$-words in a two-letter alphabet
• SIMULTANEOUS AVOIDANCE OF LARGE SQUARES AND FRACTIONAL POWERS IN INFINITE BINARY WORDS
• A linear-time algorithm to decide whether a binary word contains an overlap
• Automatic Sequences
• The number of binary cube-free words of length up to 47 and their numerical analysis
• The Goulden—Jackson cluster method: extensions, applications and implementations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial versus exponential growth in repetition-free binary words