Root clustering of words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 3, pp. 267-280.

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.

DOI : 10.1051/ita/2014009
Classification : 68Q45, 68R15
Mots-clés : periodicity of words, primitivity of words, roots of words, classification of words 
@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},
     pages = {267--280},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {3},
     year = {2014},
     doi = {10.1051/ita/2014009},
     mrnumber = {3302488},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2014009/}
}
TY  - JOUR
AU  - Lischke, Gerhard
TI  - Root clustering of words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2014
SP  - 267
EP  - 280
VL  - 48
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2014009/
DO  - 10.1051/ita/2014009
LA  - en
ID  - ITA_2014__48_3_267_0
ER  - 
%0 Journal Article
%A Lischke, Gerhard
%T Root clustering of words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2014
%P 267-280
%V 48
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2014009/
%R 10.1051/ita/2014009
%G en
%F 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) no. 3, pp. 267-280. doi : 10.1051/ita/2014009. http://archive.numdam.org/articles/10.1051/ita/2014009/

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

Cité par Sources :