fixed points; morphic primitivity; complexity
We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in $\mathcal O(m\cdot n)$, where $n$ is the length of the word and $m$ the size of the alphabet.
 Head, T., Lando, B.: Fixed and stationary $\omega$-words and $\omega$-languages
. In: The Book of L (G. Rozenberg and A. Salomaa, eds.), Springer-Verlag, Berlin - Heidelberg 1986, pp. 147-156. Zbl 0586.68063