Complexity of testing morphic primitivity
Kybernetika (2013)
- Volume: 49, Issue: 2, page 216-223
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topHolub, Štěpán, and Matocha, Vojtěch. "Complexity of testing morphic primitivity." Kybernetika 49.2 (2013): 216-223. <http://eudml.org/doc/260650>.
@article{Holub2013,
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.},
author = {Holub, Štěpán, Matocha, Vojtěch},
journal = {Kybernetika},
keywords = {fixed points; morphic primitivity; complexity; fixed points; morphic primitivity; complexity},
language = {eng},
number = {2},
pages = {216-223},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Complexity of testing morphic primitivity},
url = {http://eudml.org/doc/260650},
volume = {49},
year = {2013},
}
TY - JOUR
AU - Holub, Štěpán
AU - Matocha, Vojtěch
TI - Complexity of testing morphic primitivity
JO - Kybernetika
PY - 2013
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 2
SP - 216
EP - 223
AB - 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.
LA - eng
KW - fixed points; morphic primitivity; complexity; fixed points; morphic primitivity; complexity
UR - http://eudml.org/doc/260650
ER -
References
top- Ehrenfeucht, A., Rozenberg, G., 10.1016/0020-0190(79)90135-2, Inform. Process. Lett. 9 (1979), 86-88. Zbl0414.68022MR0542652DOI10.1016/0020-0190(79)90135-2
- Head, T., 10.1080/00207168108803273, Internat. J. Comput. Math. 10 (1981/82), 103-107. Zbl0472.68034MR0645626DOI10.1080/00207168108803273
- Head, T., Lando, B., Fixed and stationary -words and -languages., In: The Book of L (G. Rozenberg and A. Salomaa, eds.), Springer-Verlag, Berlin - Heidelberg 1986, pp. 147-156. Zbl0586.68063
- Holub, Š., 10.1016/j.disc.2009.03.019, Discrete Math. 309 (2009), 5069-5076. MR2548908DOI10.1016/j.disc.2009.03.019
- Reidenbach, D., Schneider, J. C., 10.1016/j.tcs.2009.01.020, Theoret. Comput. Sci. 410 (2009), 2148-2161. Zbl1166.68036MR2519302DOI10.1016/j.tcs.2009.01.020
- Shallit, J., Wang, M. W., 10.1016/S0304-3975(01)00092-5, Theoret. Comput. Sci. 270 (2002), 659-675. Zbl0988.68141MR1871089DOI10.1016/S0304-3975(01)00092-5
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.