Geodesic
Complexity of testing morphic primitivity
Kybernetika, Tome 49 (2013) no. 2, pp. 216-223 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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},
     year = {2013},
     volume = {49},
     number = {2},
     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
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
%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/

[1] Ehrenfeucht, A., Rozenberg, G.: Finding a homomorphism between two words is NP-complete. Inform. Process. Lett. 9 (1979), 86-88. | DOI | MR | Zbl

[2] Head, T.: Fixed languages and the adult languages of OL schemes. Internat. J. Comput. Math. 10 (1981/82), 103-107. | DOI | MR | Zbl

[3] Head, T., Lando, B.: Fixed and stationary $\omega$-words and $\omega$-languages. In: The Book of L (G. Rozenberg and A. Salomaa, eds.), Springer-Verlag, Berlin - Heidelberg 1986, pp. 147-156. | Zbl

[4] Holub, Š.: Polynomial algorithm for fixed points of nontrivial morphisms. Discrete Math. 309 (2009), 5069-5076. | DOI | MR

[5] Reidenbach, D., Schneider, J. C.: Morphically primitive words. Theoret. Comput. Sci. 410 (2009), 2148-2161. | DOI | MR | Zbl

[6] Shallit, J., Wang, M. W.: On two-sided infinite fixed points of morphisms. Theoret. Comput. Sci. 270 (2002), 659-675. | DOI | MR | Zbl