Subword complexity and power avoidance (Q2326389)

The authors study the subword complexity of \(\alpha\)-power-free words for different values of \(\alpha\) and different alphabets, prove a wealth of results and state several conjectures and open questions. They prove e.g. that the Thue-Morse word has the minimum possible subword complexity over all overlap-free binary words, more precisely for \(2^+ \le \alpha \le 7/3\), and the twisted Thue-Morse word has the maximum possible subword complexity over all overlap-free binary words, but no binary word has maximal complexity for \(\alpha = 7/3\). No square-free ternary word has smaller subword complexity for all \(n \ge 1\) than the ternary Thue word. The recently constructed 1-2-bonacci word has the minimal possible subword complexity (\(6n-6\)) over all symmetric square-free ternary words, where symmetric means that the set of factors is invariant under exchanging letters. Other questions and results concern the asymptotic growth of the subword complexity, the minimal critical exponent of words with given complexity, properties of the Arshon word, words of complexity \(2n\) and \(2n+1\), binary \((7/3)^+\)-power-free words and ternary \((7/4)^+\)-power-free words with exponential complexity, the Restivo-Salemi property of power-free languages, etc.