×

Periodicity and the golden ratio. (English) Zbl 0913.68162

Summary: We prove a periodicity theorem on words that has strong analogies with the critical factorization theorem. The critical factorization theorem states, roughly speaking, a connection between local and global periods of a word; the local period at any position in the word is there defined as the shortest repetition (a square) “centered” in that position. We here take into account a different notion of local period by considering, for any position in the word, the shortest repetition “immediately to the left” from that position. In this case a repetition which is a square does not suffices and the golden ratio \(\varphi\) (more precisely its square \(\varphi^2= 2.618\dots)\) surprisingly appears as a threshold for establishing a connection between local and global periods of the word. We further show that the number \(\varphi^2\) is tight for this result. Two applications are then derived. In the first we give a characterization of ultimately periodic infinite words. The second application concerns the topological perfectness of some families of infinite words.

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Cesari, Y.; Vincent, M., Une caractérisation des mots Périodiques, C.R. acad. sc. Paris, Série A t., 286, 1175-1177, (1978) · Zbl 0392.20039
[2] Choffrut, C.; Karhumäki, J., Combinatorics of words, () · Zbl 0901.68096
[3] Crochemore, M.; Rytter, W., Squares, cubes and time-space efficient string-searching, Algorithmica, 13, 405-425, (1995) · Zbl 0849.68044
[4] Currie, J.D., Amer. math. monthly, 100, 790-793, (1993)
[5] Currie, J.D., On the structure and extendibility of k-power free words, Eur. J. combin., 16, 111-124, (1995) · Zbl 0824.68094
[6] J.D. Currie, R. Shelton, On the structure and extendibility of k-power free words II, preprint.
[7] Currie, J.D.; Shelton, R., Cantor sets and Dejean’s conjecture, J. automata, languages and combinatorics, 1, 2, 113-127, (1996) · Zbl 0867.68068
[8] de Luca, A., A combinatorial property of the Fibonacci words, Inform. process. lett., 12, 4, 195-195, (1981)
[9] Duval, J.P., Périodes et Répetitions des mots du monoide libre, Theoret. comput. sci., 9, 17-26, (1979) · Zbl 0402.68052
[10] Fife, E.D., Binary sequence which contains no bbb, Trans. amer. math. soc., 261, 1, 115-136, (1980) · Zbl 0464.05018
[11] Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, (1995), Addison-Wesley Reading, MA
[12] Galil, Z.; Seiferas, J., Time-space optimal string matching, J. comput. system sci., 26, 280-294, (1983) · Zbl 0509.68101
[13] Lothaire, M., Combinatorics on words, () · Zbl 1001.68093
[14] Mignosi, F.; Pirillo, G., Repetitions in the Fibonacci infinite word, RAIRO theor. inform. appl., 26, 3, 199-204, (1992) · Zbl 0761.68078
[15] Mignosi, F.; Restivo, A.; Salemi, S., A periodicity theorem on words and applications, () · Zbl 1193.68202
[16] Restivo, A.; Salemi, S., Overlap free words on two symbols, (), 198-206
[17] J. Shallit, Private Communication, 1994.
[18] Shelton, R.; Sony, R., Aperiodic words on the three symbols 1, 2, 3, J. reine angew. math., 321, 195-209, (1982)
[19] Shelton, R.; Sony, R., (), 101-118
[20] Shelton, R., J. reine angew. math., 330, 44-52, (1984)
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.