Complexity of testing morphic primitivity

Vojtěch Matocha, Štěpán Holub

We analyze the algorithm in [Holub, 2009], which decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in O(…