2010/06/21 by Michael Domaratzki, Narad Rampersad, Domaratzki, Michael +1
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1006.4104
openalex publication_date 2010/06/21 · arxiv created 2010/06/24 · arxiv updated 2010/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.