Gerhard Lischke: Generalized Periodicity and Primitivity of Words, their Roots and Distances

Abstract In this talk we give an overview about results for periodicity and primitivity of words and their generalizations obtained during the last decade, some recent results about distances and numbers of such words, and point out some open questions. The generalizations yield to six kinds of periodicity and six kinds of primitivity of words which on their part give cause to define six kinds of roots of words and languages. We give the inclusionship between the sets of generalized primitive resp. periodic words and the prefix relationship between the different roots of a word. It remains open whether there exist words the six roots of them are different each other. The context-sensitivity of our sets of generalized periodic words and primitive words is trivial, and it is easy to see that the sets of generalized periodic words are not context-free. In contrast to this, the question of context-freeness of the sets of generalized primitive words is open. On the other side, their integration into the system of Marcus contextual languages is clear. The decidability of each of our sets of generalized periodic resp. primitive words has a quadratic lower bound time complexity. This is also optimal for two of our sets, and for the remaining sets this optimality remains open. Between the complexity of a language and that of each of its six roots there can be an arbitrarily large gap, from which fact we follow that there exist regular languages all of whose roots are not even context-sensitive. The distance in the sense of Hamming from an arbitrary word to one of the sets of primitive words is shown to be at most one. In the opposite direction, from primitive words to generalized periodic words this distance depends from the lengths of the words and from the cardinality of the alphabet. Finally, we examine so-called distance sets between the different kinds of generalized periodic words and determine the number of gene- ralized periodic words of given length.