Root clustering of words∗
Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität Jena,
Ernst-Abbe-Platz 1-4, 07743 Jena, Germany.
Accepted: 14 March 2014
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.
Mathematics Subject Classification: 68Q45 / 68R15
Key words: Periodicity of words / primitivity of words / roots of words / classification of words
This work was supported by the Fellowship Program of the Japan Society for Promotion of Science (JSPS) under No. S-11717. Parts of it have been presented at the Second Russian Finnish Symposium on Discrete Mathematics in Turku 2012 under the title k-root words and their clusters and at the 22nd Theorietag Automata and Formal Languages in Prague under the title Lohmann words and more clusters of words.
© EDP Sciences 2014