On the additive complexity of a Thue-Morse like sequence

2018/02/10 by Chen, Jin, Wen, Zhixiong, Wu, Wen · 1 citation
#05D99 #11B85 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1802.03610

Abstract

In this paper, we study the additive complexity ρ⁺_t(n) of a Thue-Morse like sequence t=σ^∞(0) with the morphism σ: 0→ 01, 1→ 12, 2→ 20. We show that ρ⁺_t(n)=2\lfloorlog₂(n)\rfloor+3 for all integers n≥ 1. Consequently, (ρ_t(n))_{n≥ 1} is a 2-regular sequence.

Cited by

• Net Occurrences in Fibonacci and Thue-Morse Words

Related

• On the 2-Abelian Complexity of the Thue-Morse Word
• On two conjectures of Shallit about Thue-Morse-like sequences
• Permutation Complexity of the Thue-Morse Word
• On the 2-binomial complexity of the generalized Thue-Morse words
• On the maximum order complexity of Thue-Morse and Rudin-Shapiro\n sequences along polynomial values