Article (Scientific journals)
How far away must forced letters be so that squares are still avoidable?
Rosenfeld, Matthieu
2020In Mathematics of Computation, 89 (326), p. 3057-3071
Peer Reviewed verified by ORBi
 

Files


Full Text
S0025-5718-2020-03535-2.pdf
Publisher postprint (241.29 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[en] We describe a new nonconstructive 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 a 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 nonconstructive (e.g., the Thue-list coloring number of the infinite path). © 2020 American Mathematical Society.
Disciplines :
Mathematics
Author, co-author :
Rosenfeld, Matthieu ;  Université de Liège - ULg
Language :
English
Title :
How far away must forced letters be so that squares are still avoidable?
Publication date :
2020
Journal title :
Mathematics of Computation
ISSN :
0025-5718
eISSN :
1088-6842
Publisher :
American Mathematical Society, United States
Volume :
89
Issue :
326
Pages :
3057-3071
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 02 January 2021

Statistics


Number of views
29 (1 by ULiège)
Number of downloads
1 (1 by ULiège)

Scopus citations®
 
0
Scopus citations®
without self-citations
0
OpenCitations
 
0

Bibliography


Similar publications



Contact ORBi