The Lempel-Ziv Complexity of Fixed Points of Morphisms

The Lempel–Ziv complexity is a fundamental measure of complexity for words, closely connected with the famous LZ77, LZ78 compression algorithms. 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 characterisation of the complexity classes which are Θ(1), Θ(logn), and Θ(n$$^{\rm 1/{\it k}}$$), k ∈ ℕ, k ≥2, depending on the …