Subword complexity and power avoidance

Abstract

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 $(\frac{7}{3})$-power-free binary words, but not over all $(\frac{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 $(\frac{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 \textit{symmetric} square-free ternary words.

29 pages. Submitted to TCS

References in corpus (1)

• Fife's Theorem Revisited

Cited by in corpus (4)

• Upper Bound for Palindromic and Factor Complexity of Rich Words
• Transition Property for $\alpha$-Power Free Languages with $\alpha \ge 2$ and $k\ge 3$ Letters
• The number of primitive words of unbounded exponent in the language of an HD0L-system is finite
• Construction of a bi-infinite power free word with a given factor and a non-recurrent letter