Scattered Subword Complexity of Non-Primitive Words
Szilárd Zsolt Fazekas, Benedek Nagy · University of Debrecen Electronic Archive (University of Debrecen) · 2008
In this paper we analyze primitive words from the point of view of their scattered subwords. The language of primitive words has been the subject of numerous studies. It is the language of the words that are not proper powers of another word. First we take a look at the Parikh-vectors of these words, that is, we consider the commutative closure of languages formed by primitive words. After first looking at the shortest (one letter) subwords we move on towards giving necessary conditions for a word to be non-primitive in terms of scattered subword multiplicity. Furthermore, we prove that knowing the multiplicity of every word in a fixed set of words as scattered subwords in some word $w$ is not enough to decide whether $w$ is primitive or not.