The LempelZiv Complexity of Fixed Points of Morphisms

The LempelZiv complexity is a fundamental measure of complexity for words, closely connected with the famous LZ77 compression algorithm. We investigate this complexity measure for one of the most important families of infinite words in combinatorics, namely, the fixed points of morphisms. We give a complete characterization of the complexity classes which are $\Theta(1)$, $\Theta(\log n)$, and $\Theta(n^{1/k})$, $k \in \mathbb{N}$, $k\ge 2$, …