Generating square-free words efficiently

DOI10.1016/J.TCS.2015.07.027MaRDI QIDQ496050zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Arseny M. Shur

Publication date 16 September 2015

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

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

zbMATH Keywords

string algorithmsrandom wordsquare-free word

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Constructing words with high distinct square densities
• Square-free shuffles of words
• Counting ternary square-free words quickly
• Square-free words obtained from prefixes by permutations
• Extremal square-free words
• On shuffled-square-free words
• scientific article; zbMATH DE number 3932412
• scientific article; zbMATH DE number 3977002
• Square-free partial words
• Avoiding letter patterns in ternary square-free words

Cites work

• A constructive proof of the general Lovász local lemma
• Application of entropy compression in pattern avoidance
• Avoiding approximate repetitions with respect to the longest common subsequence distance
• Growth of power-free languages over large alphabets
• Growth properties of power-free languages
• Nonrepetitive sequences on arithmetic progressions
• Two-Sided Bounds for the Growth Rates of Power-Free Languages

Cited in

(4)

• The undirected repetition threshold and undirected pattern avoidance
• Approaching repetition thresholds via local resampling and entropy compression
• Non-constructive upper bounds for repetition thresholds
• On shuffled-square-free words

This page was built for publication: Generating square-free words efficiently

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