Polynomial versus exponential growth in repetition-free binary words

DOI10.1016/J.JCTA.2003.12.004MaRDI QIDQ598459zbMATH OpenOpenAlexFDO

Authors Juhani Karhumäki, Jeffrey 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)

Abstract: It is known that the number of overlap-free binary words of length n grows polynomially, while the number of cubefree binary words grows exponentially. We show that the dividing line between polynomial and exponential growth is 7/3. More precisely, there are only polynomially many binary words of length n that avoid 7/3-powers, but there are exponentially many binary words of length n that avoid (7/3+)-powers. This answers an open question of Kobayashi from 1986.

Recommendations

• Growth rate of binary words avoiding \(xxx^{R}\)
• Fewest repetitions versus maximal-exponent powers in infinite binary words
• A characterization of morphic words with polynomial growth
• Binary patterns in binary cube-free words: avoidability and growth
• On the growth rate of words in generalized Thue-Morse sequence
• A note on constructing infinite binary words with polynomial subword complexity
• scientific article; zbMATH DE number 1222604
• On repetition-free binary words of minimal density
• scientific article; zbMATH DE number 7559450
• The polynomial hierarchy for some structures over the binary words

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3912631 (Why is no real title available?)
• scientific article; zbMATH DE number 512830 (Why is no real title available?)
• scientific article; zbMATH DE number 1919522 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 1361493 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A linear-time algorithm to decide whether a binary word contains an overlap
• Automatic Sequences
• Enumeration of irreducible binary words
• On repetition-free binary words of minimal density
• On repetitions of blocks in binary sequences
• Overlap-free words and finite automata
• Repetition-free words
• SIMULTANEOUS AVOIDANCE OF LARGE SQUARES AND FRACTIONAL POWERS IN INFINITE BINARY WORDS
• Sur un théorème de Thue
• The Goulden—Jackson cluster method: extensions, applications and implementations
• The number of binary cube-free words of length up to 47 and their numerical analysis
• The structure of the set of cube-free \(Z\)-words in a two-letter alphabet
• Uniformly growing k-th power-free homomorphisms

Cited in

(41)

• Binary patterns in binary cube-free words: avoidability and growth
• Growth properties of power-free languages
• On Dejean's conjecture over large alphabets
• The first-order theory of binary overlap-free words is decidable
• Growth of repetition-free words -- a review
• Pseudoperiodic words and a question of Shevelev
• Pattern avoidance: themes and variations
• scientific article; zbMATH DE number 7559450 (Why is no real title available?)
• The critical exponent functions
• Critical exponent of binary words with few distinct palindromes
• Two-Sided Bounds for the Growth Rates of Power-Free Languages
• Efficient lower bounds on the number of repetition-free words
• Letter frequency in infinite repetition-free words
• On the entropy and letter frequencies of powerfree words
• On maximal repetitions of arbitrary exponent
• Avoiding or limiting regularities in words
• Growth rates of power-free languages
• Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices
• Infinite words containing the minimal number of repetitions
• Fewest repetitions versus maximal-exponent powers in infinite binary words
• Infinite words containing squares at every position
• A generator of morphisms for infinite words
• Minimal critical exponent of quasiperiodic words
• Deciding context equivalence of binary overlap-free words in linear time
• Enumeration of irreducible binary words
• Growth rates of complexity of power-free languages
• Avoiding large squares in infinite binary words
• The number of threshold words on \(n\) letters grows exponentially for every \(n \geq 27\)
• Antisquares and critical exponents
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• On the number of \(\alpha \)-power-free binary words for \(2<\alpha \leq 7/3\)
• Subword complexity and power avoidance
• Overlap-free words and spectra of matrices
• Power-free complementary binary morphisms
• Relations on words
• The repetition threshold for binary rich words
• Interview with Jeffrey Shallit
• On patterns occurring in binary algebraic numbers
• Fewest repetitions in infinite binary words
• Transition property for cube-free words
• Lengths of extremal square-free ternary words

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598459)