Polynomial versus exponential growth in repetition-free binary words

DOI10.1016/J.JCTA.2003.12.004zbMATH Open1065.68080arXivmath/0304095OpenAlexW2084593271MaRDI QIDQ598459FDOQ598459

Authors: Juhani Karhumäki, Jeffrey Shallit 

Publication date: 6 August 2004

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

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.

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

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

zbMATH Keywords

CubefreeExponential growthFractional powerPolynomial growthRepetition-free

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

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

Cited In (41)

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