RAIRO - Theoretical Informatics and Applications

Table of Contents - January 2012 - Volume 46, Issue 01 (Special issue dedicated to the 13th "Journées Montoises d'Informatique Théorique")  

Research Article

On abelian versions of critical factorization theorem ∗

Sergey Avgustinovicha1, Juhani Karhumäkia2a3 and Svetlana Puzyninaa1a2a3

a1 Sobolev Institute of Mathematics, 630090 Novosibirsk, Russia. avgust@math.nsc.ru

a2 University of Turku, Department of Mathematics, 20014 Turku, Finland; svepuz@utu.fi

a3 Turku Centre for Computer Science, 20014 Turku, Finland; karhumak@utu.fi

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.

(Received November 2 2010)

(Accepted August 2 2011)

(Online publication September 22 2011)

Key Words:

  • Combinatorics on words;
  • periodicity;
  • central factorization theorem;
  • abelian properties of words.

Mathematics Subject Classification:

  • 68R15

Footnotes

∗  Supported in part by the Academy of Finland under the grant 121419, by Finnish Cultural Foundation, by Russian Foundation of Basic Research (grants 10-01-00424, 09-01-00244).