Periodicity and roots of transfinite strings
Carton, Olivier ; Choffrut, Christian
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 525-533 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.

Publié le : 2001-01-01
Classification:  68R15 
@article{ITA_2001__35_6_525_0,
     author = {Carton, Olivier and Choffrut, Christian},
     title = {Periodicity and roots of transfinite strings},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {35},
     year = {2001},
     pages = {525-533},
     mrnumber = {1922293},
     zbl = {1005.68120},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2001__35_6_525_0}
}

Carton, Olivier; Choffrut, Christian. Periodicity and roots of transfinite strings. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) pp. 525-533. http://gdmltest.u-ga.fr/item/ITA_2001__35_6_525_0/

[1] A. Carpi and A. De Luca, Periodic-like words, periodicity and boxes. Acta Informatica 37 (2001) 597-618. | MR 1830469 | Zbl 0973.68192

[2] Y. Césari and M. Vincent, Une caractérisation des mots périodiques. C. R. Acad. Sci. Paris A (1978) 1175-1177. | MR 501107 | Zbl 0392.20039

[3] C. Choffrut and S. Horváth, Transfinite equations in transfinite strings, 625-649. | MR 1781851 | Zbl 1007.68140

[4] J.P. Duval, Périodes et répétitions des mots du monoïde libre. Theoret. Comput. Sci. 9 (1979) 17-26. | MR 535121 | Zbl 0402.68052

[5] J.P. Duval, Mots de Lyndon et périodicité. RAIRO: Theoret. Informatics Appl. 14 (1980) 181-191. | Numdam | MR 581676 | Zbl 0444.20048

[6] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 3 (1965) 109-114. | MR 174934 | Zbl 0131.30203

[7] D. Giammarresi, S. Mantaci, F. Mignosi and A. Restivo, A periodicity theorem fro trees. Theoret. Comput. Sci. 1-2 (1998) 145-181. | MR 1638652 | Zbl 0913.68150

[8] D. Klaua, Allgemeine Mengenlehre. Akademie Verlag (1969). | MR 242680 | Zbl 0165.31204

[9] J.G. Rosenstein, Linear ordering. Academic Press, New York (1982). | MR 662564 | Zbl 0488.04002

[10] W. Sierpiński, Cardinal and Ordinal Numbers. Warsaw: PWN (1958). | MR 95787 | Zbl 0083.26803