Growth of repetition-free words -- a review

DOI10.1016/j.tcs.2005.03.039zbMath1078.68112OpenAlexW2038914003MaRDI QIDQ2484440

Jean Berstel

Publication date: 1 August 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.03.039

zbMATH Keywords

Combinatorics on wordsSquare-free wordsOverlap-free wordsRepetitions in words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (14)

Overlap-free words and spectra of matrices ⋮ On the entropy and letter frequencies of powerfree words ⋮ Existence of finite test-sets for \(k\)-power-freeness of uniform morphisms ⋮ Growth of power-free languages over large alphabets ⋮ Growth of power-free languages: numerical and asymptotic bounds ⋮ Volume formula and growth rates of the balls of strings under the edit distances ⋮ Square-free words obtained from prefixes by permutations ⋮ Exact computation of joint spectral characteristics of linear operators ⋮ On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters ⋮ Growth properties of power-free languages ⋮ Binary words avoiding the pattern AABBCABBA ⋮ Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices ⋮ Two-Sided Bounds for the Growth Rates of Power-Free Languages ⋮ Stability of Linear Problems: Joint Spectral Radius of Sets of Matrices

Uses Software

• OEIS
• JAN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial versus exponential growth in repetition-free binary words
• A propos d'une conjecture de F. Dejean sur les répétitions dans les mots
• The entropy of square-free words
• Sequences generated by infinitely iterated morphisms
• Square-free words on partially commutative free monoids
• Enumeration of irreducible binary words
• Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters
• Overlap-free words and finite automata
• On the number of Abelian square-free words on four letters
• There exist binary circular \(5/2^+\) power free words of every length
• A unified approach to word occurrence probabilities
• Uniformly growing k-th power-free homomorphisms
• Motif statistics.
• On the entropy and letter frequencies of ternary square-free words
• CONJECTURES AND RESULTS ON MORPHISMS GENERATING k-POWER-FREE WORDS
• ON ABELIAN POWER-FREE MORPHISMS
• NON-REPETITIVE SEQUENCES ON THREE SYMBOLS
• 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
• Abelian squares are avoidable on 4 letters
• Developments in Language Theory
• On the synchronizing properties of certain prefix codes
• Partially abelian squarefree words

This page was built for publication: Growth of repetition-free words -- a review