COMPLEXITY OF TESTING MORPHIC PRIMITIVITY
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 O(m . n), where n is the length of the word and m the size of the alphabet.
complexity morphic primitivity fixed points