Generating square-free words efficiently

DOI10.1016/J.TCS.2015.07.027zbMATH Open1330.68361DBLPjournals/tcs/Shur15OpenAlexW2192358462WikidataQ64357142 ScholiaQ64357142MaRDI QIDQ496050FDOQ496050

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

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

zbMATH Keywords

string algorithmsrandom wordsquare-free word

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

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

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)