Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T09:35:50.316Z Has data issue: false hasContentIssue false
  • English
  • Français

Root clustering of words∗

Published online by Cambridge University Press:  23 May 2014

Gerhard Lischke
Gerhard Lischke*
Affiliation:
Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 1-4, 07743 Jena, Germany.. [email protected]
Get access

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.

Keywords

Periodicity of wordsprimitivity of wordsroots of wordsclassification of words
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 3: Special issue in the honor of the 14th “Journées montoises d’informatique théorique”. I. , July 2014 , pp. 267 - 280
Copyright
© EDP Sciences 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ito, M. and Lischke, G., Generalized periodicity and primitivity for words. Math. Log. Quart. 53 (2007) 91–106; Corrigendum in Math. Log. Quart. 53 (2007) 642–643. Google Scholar
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.
Lischke, G., Primitive words and roots of words. Acta Univ. Sapientiae, Informatica 3 (2011) 5–34. Google Scholar
G. Lohmann, e-mail to G. Lischke (2010).
G. Lohmann, Program packet LIMA, Apolda (2010). Improvements 2012.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Mass. (1983).
Lyndon, R.C. and Schützenberger, M.P., On the equation a M = b Nc P in a free group. Michigan Math. J. 9 (1962) 289–298. Google Scholar
H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung (1991).
S.S. Yu, Languages and Codes. Tsang Hai Book Publishing Co., Taichung (2005).