Periodic-like words, periodicity, and boxes |
| |
Authors: | Arturo Carpi Aldo de Luca |
| |
Affiliation: | (1) Istituto di Cibernetica del CNR, via Toiano 6, 80072 Arco Felice (NA), Italy (e-mail: arturo@arturo.cib.na.cnr.it) , IT;(2) Dipartimento di Matematica dell'Università di Roma “La Sapienza”, piazzale Aldo Moro 2, 00185 Roma, Italy and Centro Interdisciplinare “B. Segre”, Accademia dei Lincei, via della Lungara 10, 00100 Roma, Italy (e-mail: deluca@mat.uniromA1.it) , IT |
| |
Abstract: | We introduce the notion of periodic-like word. It is a word whose longest repeated prefix is not right special. Some different characterizations of this concept are given. In particular, we show that a word w is periodic-like if and only if it has a period not larger than , where is the least non-negative integer such that any prefix of w of length $geq R'_{w}$ is not right special. We derive that if a word w has two periods , then also the greatest common divisor of p andq is a period ofw. This result is, in fact, an improvement of the theorem of Fine and Wilf. We also prove that the minimal period of a word w is equal to the sum of the minimal periods of its components in a suitable canonical decomposition in periodic-like subwords. Moreover, we characterize periodic-like words having the same set of proper boxes, in terms of the important notion of root-conjugacy. Finally, some new uniqueness conditions for words, related to the maximal box theorem are given. Received: 10 July 2000 / Accepted: 24 January 2001 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|