Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
fixed points; morphic primitivity; complexity
fixed points; morphic primitivity; complexity
Summary:
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.
References:
[1] Ehrenfeucht, A., Rozenberg, G.: Finding a homomorphism between two words is NP-complete. Inform. Process. Lett. 9 (1979), 86-88. DOI 10.1016/0020-0190(79)90135-2 | MR 0542652 | Zbl 0414.68022
[2] Head, T.: Fixed languages and the adult languages of OL schemes. Internat. J. Comput. Math. 10 (1981/82), 103-107. DOI 10.1080/00207168108803273 | MR 0645626 | Zbl 0472.68034
[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 0586.68063
[4] Holub, Š.: Polynomial algorithm for fixed points of nontrivial morphisms. Discrete Math. 309 (2009), 5069-5076. DOI 10.1016/j.disc.2009.03.019 | MR 2548908
[5] Reidenbach, D., Schneider, J. C.: Morphically primitive words. Theoret. Comput. Sci. 410 (2009), 2148-2161. DOI 10.1016/j.tcs.2009.01.020 | MR 2519302 | Zbl 1166.68036
[6] Shallit, J., Wang, M. W.: On two-sided infinite fixed points of morphisms. Theoret. Comput. Sci. 270 (2002), 659-675. DOI 10.1016/S0304-3975(01)00092-5 | MR 1871089 | Zbl 0988.68141
Search
Partner of
