Root clustering of words

Gerhard Lischke

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

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

Abstract

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

How to cite

top

Lischke, 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. [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. [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. [3] G. Lischke, Primitive words and roots of words. Acta Univ. Sapientiae, Informatica 3 (2011) 5–34. Zbl1234.68224
  4. [4] G. Lohmann, e-mail to G. Lischke (2010). 
  5. [5] G. Lohmann, Program packet LIMA, Apolda (2010). Improvements 2012. 
  6. [6] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading Mass. (1983). Zbl0514.20045MR675953
  7. [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. [8] H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung (1991). Zbl0746.20050MR1090325
  9. [9] S.S. Yu, Languages and Codes. Tsang Hai Book Publishing Co., Taichung (2005). 

NotesEmbed ?

top

You must be logged in to post comments.