×

Everywhere \(\alpha \)-repetitive sequences and Sturmian words. (English) Zbl 1187.68369

Summary: 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 \(\alpha \)-repetitive sequences. Such a sequence is defined by the property that there exists an integer \(N\geq 2\) such that every length-\(N\) factor has a repetition of order \(\alpha \) as a prefix. If each repetition is of order strictly larger than \(\alpha \), then the sequence is called everywhere \(\alpha ^{+}\)-repetitive. In both cases, the number of distinct minimal \(\alpha \)-repetitions (or \(\alpha ^{+}\)-repetitions) occurring in the sequence is finite.
A natural question regarding global regularity is to determine the least number, denoted by \(M(\alpha )\), of distinct minimal \(\alpha \)-repetitions such that an \(\alpha \)-repetitive sequence is not necessarily ultimately periodic. We call the everywhere \(\alpha \)-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(\alpha )\) for \(1\leq \alpha \leq 15/7\).

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Lothaire, M., ()
[2] Mignosi, F.; Restivo, A.; Salemi, S., Periodicity and the Golden ratio, Theoret. comput. sci., 204, 1-2, 153-167, (1998) · Zbl 0913.68162
[3] Karhumäki, J.; Lepistö, A.; Plandowski, W., Locally periodic versus globally periodic infinite words, J. combin. theory ser. A, 100, 250-264, (2002) · Zbl 1011.68070
[4] A. Lepistö, On relations between local and global periodicity, Ph.D. Dissertation, Turku Centre for Computer Science, 2003
[5] Saari, K., Everywhere \(\alpha\)-repetitive sequences and Sturmian words, (), 363-372 · Zbl 1188.68218
[6] Choffrut, C.; Karhumäki, J., Combinatorics on words, (), 329-438
[7] K. Saari, On the periodicity and frequency of infinite words, Ph.D. Dissertation, Turku Centre for Computer Science, 2008
[8] Allouche, J.-P.; Shallit, J., Automatic sequences. theory, applications, generalizations, (2003), Cambrige University Press Cambridge · Zbl 1086.11015
[9] Wen, Z.-X.; Wen, Z.-Y., Some properties of the singular words of the Fibonacci word, European J. combin., 15, 587-598, (1994) · Zbl 0823.68087
[10] Knuth, D.E.; Morris, J.H.; Pratt, V.R., Fast pattern matching in strings, SIAM J. comput., 6, 2, 323-350, (1977) · Zbl 0372.68005
[11] Berthé, V.; Holton, C.; Zamboni, L.Q., Initial powers of Sturmian sequences, Acta arith., 122, 4, 315-347, (2006) · Zbl 1117.37005
[12] Krieger, D.; Shallit, J., Every real number greater than 1 is a critical exponent, Theoret. comput. sci., 381, 1-3, 177-182, (2007) · Zbl 1188.68216
[13] Carpi, A.; de Luca, A., Special factors, periodicity, and an application to Sturmian words, Acta inform., 36, 983-1006, (2000) · Zbl 0956.68119
[14] Damanik, D.; Lenz, D., The index of Sturmian sequences, European J. combin., 23, 23-29, (2002) · Zbl 1002.11020
[15] Currie, J.D.; Visentin, T.I., On abelian 2-avoidable binary patterns, Acta inform., 43, 521-533, (2007) · Zbl 1111.68094
[16] Richomme, G.; Saari, K.; Zamboni, L.Q., Standard words and abelian powers in Sturmian words, () · Zbl 1184.68378
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.