# Root clustering of words

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 3, page 267-280
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topLischke, Gerhard. "Root clustering of words." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.3 (2014): 267-280. <http://eudml.org/doc/273086>.

@article{Lischke2014,

abstract = {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.},

author = {Lischke, Gerhard},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {periodicity of words; primitivity of words; roots of words; classification of words},

language = {eng},

number = {3},

pages = {267-280},

publisher = {EDP-Sciences},

title = {Root clustering of words},

url = {http://eudml.org/doc/273086},

volume = {48},

year = {2014},

}

TY - JOUR

AU - Lischke, Gerhard

TI - Root clustering of words

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2014

PB - EDP-Sciences

VL - 48

IS - 3

SP - 267

EP - 280

AB - 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.

LA - eng

KW - periodicity of words; primitivity of words; roots of words; classification of words

UR - http://eudml.org/doc/273086

ER -

## References

top- [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. Zbl1107.68050MR2288894
- [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. Zbl1264.68099MR2789070
- [3] G. Lischke, Primitive words and roots of words. Acta Univ. Sapientiae, Informatica 3 (2011) 5–34. Zbl1234.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). Zbl0514.20045MR675953
- [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. Zbl0106.02204MR162838
- [8] H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung (1991). Zbl0746.20050MR1090325
- [9] S.S. Yu, Languages and Codes. Tsang Hai Book Publishing Co., Taichung (2005).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.