Kybernetika 49 no. 2, 216-223, 2013

Complexity of testing morphic primitivity

Štěpán Holub and Vojtěch Matocha

Abstract:

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.

Keywords:

complexity, fixed points, morphic primitivity

Classification:

68R15

paper.pdf

References:

  1. A. Ehrenfeucht and G. Rozenberg: Finding a homomorphism between two words is NP-complete. Inform. Process. Lett. 9 (1979), 86-88.   CrossRef
  2. T. Head: Fixed languages and the adult languages of OL schemes. Internat. J. Comput. Math. 10 (1981/82), 103-107.   CrossRef
  3. T. Head and B. Lando: 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.   CrossRef
  4. Š. Holub: Polynomial algorithm for fixed points of nontrivial morphisms. Discrete Math. 309 (2009), 5069-5076.   CrossRef
  5. D. Reidenbach and J. C. Schneider: Morphically primitive words. Theoret. Comput. Sci. 410 (2009), 2148-2161.   CrossRef
  6. J. Shallit and M. W. Wang: On two-sided infinite fixed points of morphisms. Theoret. Comput. Sci. 270 (2002), 659-675.   CrossRef