[en] We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time. Also different from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration problems and the relation to the theory of codes.
Disciplines :
Mathematics
Author, co-author :
Domaratzki, Michael
Rampersad, Narad ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Abelian primitive words
Publication date :
2011
Event name :
15th Conference on Developments in Language Theory
