Subword complexity and power avoidance

We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that – the Thue–Morse word has the minimum possible subword complexity over all overlap-free binary words and all ( 7 3 ) -power-free binary words, but not over all ( 7 3 ) + -power-free binary words; – the twisted Thue–Morse word has the maximum possible subword complexity over all overlap-free binary words, but no word has the maximum subword complexity over all ( 7 3 ) -power-free binary words; – if some word attains the minimum possible subword complexity over all square-free ternary words, then one such word is the ternary Thue word; – the recently constructed 1-2-bonacci word has the minimum possible subword complexity over all symmetric square-free ternary words.

Authors

• Jeffrey Shallit
• Arseny Shur

Keywords

• Combinatorics on words
• Subword complexity
• Power-free word
• Critical exponent
• Thue–Morse word