Everywhere -repetitive sequences and Sturmian words |
| |
Authors: | Kalle Saari |
| |
Institution: | aDepartment of Mathematics, University of Turku, 20014 Turku, Finland;bTurku Centre for Computer Science, University of Turku, 20014 Turku, Finland |
| |
Abstract: | Local constraints on an infinite sequence that imply global regularity are of general interest in combinatorics on words. We consider this topic by studying everywhere α-repetitive sequences. Such a sequence is defined by the property that there exists an integer N≥2 such that every length-N factor has a repetition of order α as a prefix. If each repetition is of order strictly larger than α, then the sequence is called everywhere α+-repetitive. In both cases, the number of distinct minimal α-repetitions (or α+-repetitions) occurring in the sequence is finite.A natural question regarding global regularity is to determine the least number, denoted by M(α), of distinct minimalα-repetitions such that an α-repetitive sequence is not necessarily ultimately periodic. We call the everywhere α-repetitive sequences witnessing this property optimal. In this paper, we study optimal 2-repetitive sequences and optimal 2+-repetitive sequences, and show that Sturmian words belong to both classes. We also give a characterization of 2-repetitive sequences and solve the values of M(α) for 1≤α≤15/7. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|