Geodesic
Complexity of testing morphic primitivity
Kybernetika, Tome 49 (2013) no. 2, pp. 216-223.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 68R15
Keywords: fixed points; morphic primitivity; complexity 
@article{KYB_2013__49_2_a1,
     author = {Holub, \v{S}t\v{e}p\'an and Matocha, Vojt\v{e}ch},
     title = {Complexity of testing morphic primitivity},
     journal = {Kybernetika},
     pages = {216--223},
     publisher = {mathdoc},
     volume = {49},
     number = {2},
     year = {2013},
     mrnumber = {3085393},
     zbl = {1266.68150},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2013__49_2_a1/}
}
TY  - JOUR
AU  - Holub, Štěpán
AU  - Matocha, Vojtěch
TI  - Complexity of testing morphic primitivity
JO  - Kybernetika
PY  - 2013
SP  - 216
EP  - 223
VL  - 49
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2013__49_2_a1/
LA  - en
ID  - KYB_2013__49_2_a1
ER  - 
%0 Journal Article
%A Holub, Štěpán
%A Matocha, Vojtěch
%T Complexity of testing morphic primitivity
%J Kybernetika
%D 2013
%P 216-223
%V 49
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2013__49_2_a1/
%G en
%F KYB_2013__49_2_a1
Holub, Štěpán; Matocha, Vojtěch. Complexity of testing morphic primitivity. Kybernetika, Tome 49 (2013) no. 2, pp. 216-223. http://geodesic.mathdoc.fr/item/KYB_2013__49_2_a1/