On the 2-Abelian Complexity of the Thue-Morse Word

2014/04/15 by Florian Greinecker, Greinecker, Florian · 1 citation
Computer Science · Mathematics · #11B85 (Primary) #68Q70 (Secondary) #68R15 (Secondary) #Abelian group #Algorithms and Data Compression #Combinatorics #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computer science #Concatenation (mathematics) #Discrete mathematics #FOS: Mathematics #Geometry #Mathematics #Morse code #Word (group theory) #math.CO #msc:11B85 #msc:68Q70 #msc:68R15 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1404.3906

openalex publication_date 2014/04/15 · arxiv created 2015/06/02 · arxiv updated 2015/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

We show that the 2-abelian complexity of the infinite Thue-Morse word is 2-regular, and other properties of the 2-abelian complexity, most notably that it is a concatenation of palindromes of increasing length. We also show sharp bounds for the length of unique extensions of factors of size n, occurring in the Thue-Morse word.

Citations

• Enumeration of factors in the Thue-Morse word
• Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence

Cited by

• Reduced complexities for sequences over finite alphabets

Related

• Computing the k-binomial complexity of the Thue--Morse word
• Palindromic length complexity and a generalization of Thue-Morse sequences
• Computing the k-binomial complexity of generalized Thue--Morse words
• On the 2-binomial complexity of the generalized Thue-Morse words
• Abelian Properties of Words (Extended abstract)