2012/07/21 by Daniel Goč, Daniel Goc, Kalle Saari +4
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.FL #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1207.5124
openalex publication_date 2012/07/21 · arxiv created 2012/11/06 · arxiv updated 2012/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate questions related to the presence of primitive words and Lyndon words in automatic and linearly recurrent sequences. We show that the Lyndon factorization of a k-automatic sequence is itself k-automatic. We also show that the function counting the number of primitive factors (resp., Lyndon factors) of length n in a k-automatic sequence is k-regular. Finally, we show that the number of Lyndon factors of a linearly recurrent sequence is bounded.