Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T09:23:40.174Z Has data issue: false hasContentIssue false
  • English
  • Français

On abelian versions of critical factorization theorem∗

Published online by Cambridge University Press:  22 September 2011

Sergey Avgustinovich ,
Juhani Karhumäki  and
Svetlana Puzynina
Sergey Avgustinovich
Affiliation:
Sobolev Institute of Mathematics, 630090 Novosibirsk, Russia. [email protected]
Juhani Karhumäki
Affiliation:
University of Turku, Department of Mathematics, 20014 Turku, Finland; [email protected] Turku Centre for Computer Science, 20014 Turku, Finland; [email protected]
Svetlana Puzynina
Affiliation:
Sobolev Institute of Mathematics, 630090 Novosibirsk, Russia. [email protected] University of Turku, Department of Mathematics, 20014 Turku, Finland; [email protected] Turku Centre for Computer Science, 20014 Turku, Finland; [email protected]
Get access

Abstract

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.

Keywords

Combinatorics on wordsperiodicitycentral factorization theoremabelian properties of words.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 1: Special issue dedicated to the 13th "Journées Montoises d'Informatique Théorique" , January 2012 , pp. 3 - 15
Copyright
© EDP Sciences 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Références

Avgustinovich, S.V. and Frid, A.E., Words avoiding abelian inclusions. J. Autom. Lang. Comb. 7 (2002) 3–9. Google Scholar
Césari, Y. and Vincent, M., Une caractérisation des mots périodiques. C.R. Acad. Sci. Paris, Ser. A 286 (1978) 1175–1177. Google Scholar
Cassaigne, J. and Karhumäki, J., Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Comb. 18 (1997) 497–510. Google Scholar
Cassaigne, J., Richomme, G., Saari, K. and Zamboni, L.Q., Avoiding Abelian powers in binary words with bounded Abelian complexity. Int. J. Found. Comput. Sci. 22 (2011) 905–920. Google Scholar
Duval, J.-P., Périodes et répetitions des mots du monoide libre. Theoret. Comput. Sci. 9 (1979) 17–26. Google Scholar
Karhumäki, J., Lepistö, A. and Plandowski, W., Locally periodic versus globally periodic infinite words. J. Comb. Th. (A) 100 (2002) 250–264. Google Scholar
A. Lepistö, On Relations between Local and Global Periodicity. Ph.D. thesis (2002).
M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).
Mignosi, F., Restivo, A. and Salemi, S., Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998) 153–167. Google Scholar
Richomme, G., Saari, K. and Zamboni, L., Abelian complexity of minimal subshifts. J. London Math. Soc. 83 (2011) 79–95. Google Scholar
Saari, K., Everywhere α-repetitive sequences and Sturmian words. Eur. J. Comb. 31 (2010) 177–192. Google Scholar
Toeplitz, O., Beispiele zur theorie der fastperiodischen Funktionen. Math. Ann. 98 (1928) 281–295. Google Scholar