| Title:
|
Complexity of testing morphic primitivity (English) |
| Author:
|
Holub, Štěpán |
| Author:
|
Matocha, Vojtěch |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
49 |
| Issue:
|
2 |
| Year:
|
2013 |
| Pages:
|
216-223 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
fixed points |
| Keyword:
|
morphic primitivity |
| Keyword:
|
complexity |
| MSC:
|
68R15 |
| idZBL:
|
Zbl 1266.68150 |
| idMR:
|
MR3085393 |
| . |
| Date available:
|
2013-07-22T08:43:42Z |
| Last updated:
|
2016-01-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143364 |
| . |
| Reference:
|
[1] Ehrenfeucht, A., Rozenberg, G.: Finding a homomorphism between two words is NP-complete..Inform. Process. Lett. 9 (1979), 86-88. Zbl 0414.68022, MR 0542652, 10.1016/0020-0190(79)90135-2 |
| Reference:
|
[2] Head, T.: Fixed languages and the adult languages of OL schemes..Internat. J. Comput. Math. 10 (1981/82), 103-107. Zbl 0472.68034, MR 0645626, 10.1080/00207168108803273 |
| Reference:
|
[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 |
| Reference:
|
[4] Holub, Š.: Polynomial algorithm for fixed points of nontrivial morphisms..Discrete Math. 309 (2009), 5069-5076. MR 2548908, 10.1016/j.disc.2009.03.019 |
| Reference:
|
[5] Reidenbach, D., Schneider, J. C.: Morphically primitive words..Theoret. Comput. Sci. 410 (2009), 2148-2161. Zbl 1166.68036, MR 2519302, 10.1016/j.tcs.2009.01.020 |
| Reference:
|
[6] Shallit, J., Wang, M. W.: On two-sided infinite fixed points of morphisms..Theoret. Comput. Sci. 270 (2002), 659-675. Zbl 0988.68141, MR 1871089, 10.1016/S0304-3975(01)00092-5 |
| . |
