How far away must forced letters be so that squares are still avoidable?

DOI10.1090/MCOM/3535MaRDI QIDQ5118863zbMATH OpenOpenAlexFDO

Authors Matthieu Rosenfeld

Publication date 27 August 2020

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

avoidabilitysquaressquare-free wordsquare-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Computer assisted proofs of proofs-by-exhaustion type (68V05)

Abstract: We describe a new non-constructive technique to show that squares are avoidable by an infinite word even if we force some letters from the alphabet to appear at certain occurrences. We show that as long as forced positions are at distance at least 19 (resp. 3, resp. 2) from each other then we can avoid squares over 3 letters (resp. 4 letters, resp. 6 or more letters). We can also deduce exponential lower bounds on the number of solutions. For our main Theorem to be applicable, we need to check the existence of some languages and we explain how to verify that they exist with a computer. We hope that this technique could be applied to other avoidability questions where the good approach seems to be non-constructive (e.g., the Thue-list coloring number of the infinite path).

Recommendations

• Avoiding squares over words with lists of size three amongst four symbols
• scientific article; zbMATH DE number 2051164
• Avoiding Approximate Squares
• Infinite words containing squares at every position
• Avoiding Abelian squares in partial words

Cites work

• Doubled patterns are 3-avoidable
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• New approach to nonrepetitive sequences
• Nonrepetitive colorings of graphs
• On square-free arithmetic progressions in infinite words
• Some further results on squarefree arithmetic progressions in infinite words

Cited in

(1)

• AVOIDING APPROXIMATE SQUARES

This page was built for publication: How far away must forced letters be so that squares are still avoidable?

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