Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T09:57:40.274Z 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.. gerhard.lischke@uni-jena.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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], giverise to defining six kinds of roots of a nonempty word. For 1 ≤ k ≤ 6, ak-root wordis a word which has exactly k different roots, and a k-cluster is a set ofk-rootwords u wherethe roots of u fulfil a given prefix relationship. We show thatout of the 89 different clusters that can be considered at all, in fact only 30 exist, andwe give their quasi-lexicographically smallest elements. Also we give a sufficientcondition for words to belong to the only existing 6-cluster. These words are also calledLohmann words. Further we show that, with the exception of a single cluster, each of theexisting clusters contains either only periodic words, or only primitive words.

Keywords

Periodicity of wordsprimitivity of wordsroots of wordsclassification of words

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