Root clustering of words
Lischke, Gerhard
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014), p. 267-280 / Harvested from Numdam
Access to full text

Six kinds of both of primitivity and periodicity of words, introduced by Ito and Lischke [M. Ito and G. Lischke, Math. Log. Quart. 53 (2007) 91-106; Corrigendum in Math. Log. Quart. 53 (2007) 642-643], give rise to defining six kinds of roots of a nonempty word. For 1 ≤ k ≤ 6, a k-root word is a word which has exactly k different roots, and a k-cluster is a set of k-root words u where the roots of u fulfil a given prefix relationship. We show that out of the 89 different clusters that can be considered at all, in fact only 30 exist, and we give their quasi-lexicographically smallest elements. Also we give a sufficient condition for words to belong to the only existing 6-cluster. These words are also called Lohmann words. Further we show that, with the exception of a single cluster, each of the existing clusters contains either only periodic words, or only primitive words.

Publié le : 2014-01-01
DOI : https://doi.org/10.1051/ita/2014009
Classification:  68Q45,  68R15 
@article{ITA_2014__48_3_267_0,
     author = {Lischke, Gerhard},
     title = {Root clustering of words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {48},
     year = {2014},
     pages = {267-280},
     doi = {10.1051/ita/2014009},
     mrnumber = {3302488},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2014__48_3_267_0}
}

Lischke, Gerhard. Root clustering of words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) pp. 267-280. doi : 10.1051/ita/2014009. http://gdmltest.u-ga.fr/item/ITA_2014__48_3_267_0/

[1] M. Ito and G. Lischke, Generalized periodicity and primitivity for words. Math. Log. Quart. 53 (2007) 91-106; Corrigendum in Math. Log. Quart. 53 (2007) 642-643. | MR 2288894 | Zbl 1107.68050

[2] G. Lischke, The primitivity distance of words, in Automata, Formal Languages and Algebraic Systems, edited by M. Ito, Y. Kobayashi and K. Shoji. World Scientific (2010) 125-137. | MR 2789070 | Zbl 1264.68099

[3] G. Lischke, Primitive words and roots of words. Acta Univ. Sapientiae, Informatica 3 (2011) 5-34. | Zbl 1234.68224

[4] G. Lohmann, e-mail to G. Lischke (2010).

[5] G. Lohmann, Program packet LIMA, Apolda (2010). Improvements 2012.

[6] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Mass. (1983). | MR 675953 | Zbl 0514.20045

[7] R.C. Lyndon and M.P. Schützenberger, On the equation aM = bNcP in a free group. Michigan Math. J. 9 (1962) 289-298. | MR 162838 | Zbl 0106.02204

[8] H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung (1991). | MR 1090325 | Zbl 0746.20050

[9] S.S. Yu, Languages and Codes. Tsang Hai Book Publishing Co., Taichung (2005).