1. Complexity of testing morphic primitivity Creator: Holub, Štěpán and Matocha, Vojtěch Format: bez média and svazek Type: model:article and TEXT Subject: fixed points, morphic primitivity, and complexity Language: English Description: 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. Rights: http://creativecommons.org/publicdomain/mark/1.0/ and policy:public