Complexity of testing morphic primitivity
  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(mn), where n is the length of the word and m the size of the alphabet. 
Vojt\v{e}ch Matocha, \v{S}t\v{e}p\'an Holub
cs.FL math.CO