A Separation of γ and b via Thue--Morse Words

2021/04/19 by Bannai, Hideo, Funakoshi, Mitsuru, I, Tomohiro +3 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.09985

Abstract

We prove that for n≥ 2, the size b(t_n) of the smallest bidirectional scheme for the nth Thue--Morse word t_n is n+2. Since Kutsukake et al. [SPIRE 2020] show that the size γ(t_n) of the smallest string attractor for t_n is 4 for n ≥ 4, this shows for the first time that there is a separation between the size of the smallest string attractor γ and the size of the smallest bidirectional scheme b, i.e., there exist string families such that γ= o(b).

Cited by

• Net Occurrences in Fibonacci and Thue-Morse Words

Related

• On repetitiveness measures of Thue-Morse words
• On the longest common subsequence of Thue-Morse words
• On the 2-Abelian Complexity of the Thue-Morse Word
• String Attractors for Automatic Sequences
• Gaps in the Thue--Morse word