Name
Abstract | ||
|---|---|---|
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 ϑ (more precisely its square ϑ 2 = 2.618 …) surprisingly appears as a threshold for establishing a connection between local and global periods of the word. We further show that the number ϑ 2 is tight for this result. Two applications are then derived. In the firts we give a characterization of ultimately periodic infinite words. The second application concerns the topological perfectness of some families of infinite words. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0304-3975(98)00037-1 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Combinatorics on words,Power-free words,Periodicity,golden ratio | Journal | 204 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 16 |
PageRank | References | Authors |
1.58 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Filippo Mignosi | 1 | 569 | 99.71 |
| Antonio Restivo | 2 | 697 | 107.05 |
| Sergio Salemi | 3 | 145 | 41.24 |