Efficient lower bounds on the number of repetition-free words

MaRDI QIDQ3428618zbMATH OpenFDO

Authors Roman Kolpakov

Publication date 28 March 2007

Full work available at URL https://eudml.org/doc/53302, http://www.emis.de/journals/JIS/VOL10/Kolpakov/kolpakov42.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)

Recommendations

• An improved lower bound on the number of ternary squarefree words
• On an efficient method for estimating the number of nonrepeating words
• Improved bounds on the number of ternary square-free words
• Polynomial versus exponential growth in repetition-free binary words
• scientific article; zbMATH DE number 3932412

Cited in

(13)

• Growth properties of power-free languages
• On an efficient method for estimating the number of nonrepeating words
• Binary words avoiding the pattern AABBCABBA
• On the entropy and letter frequencies of powerfree words
• Avoiding or limiting regularities in words
• Counting ternary square-free words quickly
• On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters
• Enumeration of irreducible binary words
• The number of threshold words on \(n\) letters grows exponentially for every \(n \geq 27\)
• Counting abelian squares efficiently for a problem in quantum computing
• Reduced word enumeration, complexity, and randomization
• An improved lower bound on the number of ternary squarefree words
• Improved bounds on the number of ternary square-free words

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Efficient lower bounds on the number of repetition-free words

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