On abelian versions of critical factorization theorem
Avgustinovich, Sergey ; Karhumäki, Juhani ; Puzynina, Svetlana
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 3-15 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

In the paper we study abelian versions of the critical factorization theorem. We investigate both similarities and differences between the abelian powers and the usual powers. The results we obtained show that the constraints for abelian powers implying periodicity should be quite strong, but still natural analogies exist.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2011121
Classification:  68R15 
@article{ITA_2012__46_1_3_0,
     author = {Avgustinovich, Sergey and Karhum\"aki, Juhani and Puzynina, Svetlana},
     title = {On abelian versions of critical factorization theorem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {46},
     year = {2012},
     pages = {3-15},
     doi = {10.1051/ita/2011121},
     mrnumber = {2904957},
     zbl = {1247.68200},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2012__46_1_3_0}
}

Avgustinovich, Sergey; Karhumäki, Juhani; Puzynina, Svetlana. On abelian versions of critical factorization theorem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 3-15. doi : 10.1051/ita/2011121. http://gdmltest.u-ga.fr/item/ITA_2012__46_1_3_0/

[1] S.V. Avgustinovich and A.E. Frid, Words avoiding abelian inclusions. J. Autom. Lang. Comb. 7 (2002) 3-9. | MR 1915289 | Zbl 1021.68069

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

[3] J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Comb. 18 (1997) 497-510. | MR 1455183 | Zbl 0881.68065

[4] J. Cassaigne, G. Richomme, K. Saari and L.Q. Zamboni, Avoiding Abelian powers in binary words with bounded Abelian complexity. Int. J. Found. Comput. Sci. 22 (2011) 905-920. | MR 2806895 | Zbl 1223.68089

[5] J.-P. Duval, Périodes et répetitions des mots du monoide libre. Theoret. Comput. Sci. 9 (1979) 17-26. | MR 535121 | Zbl 0402.68052

[6] J. Karhumäki, A. Lepistö and W. Plandowski, Locally periodic versus globally periodic infinite words. J. Comb. Th. (A) 100 (2002) 250-264. | MR 1940335 | Zbl 1011.68070

[7] A. Lepistö, On Relations between Local and Global Periodicity. Ph.D. thesis (2002).

[8] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002). | MR 1905123 | Zbl 1221.68183

[9] F. Mignosi, A. Restivo and S. Salemi, Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998) 153-167. | MR 1637524 | Zbl 0913.68162

[10] G. Richomme, K. Saari and L. Zamboni, Abelian complexity of minimal subshifts. J. London Math. Soc. 83 (2011) 79-95. | MR 2763945 | Zbl 1211.68300

[11] K. Saari, Everywhere α-repetitive sequences and Sturmian words. Eur. J. Comb. 31 (2010) 177-192. | MR 2552600 | Zbl 1187.68369

[12] O. Toeplitz, Beispiele zur theorie der fastperiodischen Funktionen. Math. Ann. 98 (1928) 281-295. | JFM 53.0241.02 | MR 1512405