Squarefree extensions of words

MaRDI QIDQ5154718zbMATH OpenFDO

Authors Jarosław Grytczuk, Hubert Kordulewski, Bartłomiej Pawlik

Publication date 5 October 2021

Full work available at URL https://arxiv.org/abs/2104.04841, https://cs.uwaterloo.ca/journals/JIS/VOL24/Grytczuk/grytczuk7.html

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

zbMATH Keywords

extremal wordsquarefree wordword extensionZimin word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: A word is square-free if it does not contain nonempty factors of the form $XX$. In 1906 Thue proved that there exist arbitrarily long square-free words over a $3$-letter alphabet. It was proved recently [7] that among these words there are infinitely many extremal ones, that is, having a square in every single-letter extension. We study diverse problems concerning extensions of words preserving the property of avoiding squares. Our main motivation is the conjecture stating that there are no extremal words over a $4$-letter alphabet. We also investigate a natural recursive procedure of generating square-free words by a single-letter right-most extension. We present the results of computer experiments supporting a supposition that this procedure gives an infinite square-free word over any alphabet of size at least three.

Recommendations

• Extremal square-free words
• No extremal square-free words over large alphabets
• Lengths of extremal square-free ternary words
• Maximal abelian square-free words of short length.
• scientific article; zbMATH DE number 3894492

Cites work

• Automatic Sequences
• Avoidable patterns in strings of symbols
• BLOCKING SETS OF TERMS
• Extremal overlap-free and extremal -free binary words
• Extremal square-free words
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Lengths of extremal square-free ternary words
• On ternary square-free circular words
• Pattern avoidance: themes and variations
• THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE
• The origins of combinatorics on words

Cited in

(13)

• Extremal overlap-free and extremal -free binary words
• Extremal square-free words
• Squarefree words with interior disposable factors
• Avoiding square-free words on free groups
• Constructing premaximal ternary square-free words of any level
• More on Square-free Words Obtained from Prefixes by Permutations
• scientific article; zbMATH DE number 3977002 (Why is no real title available?)
• Lengths of extremal square-free ternary words
• No extremal square-free words over large alphabets
• scientific article; zbMATH DE number 3894492 (Why is no real title available?)
• Concerning Kurosaki's squarefree word
• Extensions and reductions of squarefree words
• Square-free partial words

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Squarefree extensions of words

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