Dr. Gerhard Lischke hab. docens vendégelőadása - "The primitivity distance of words"

The primitivity distance of words Gerhard Lischke Institute of Informatics, Faculty of Mathematics and Informatics, Friedrich Schiller University Jena, Ernst-Abbe-Platz 1-4, D-07743 Jena, Germany e-mail: lischke@minet.uni-jena.de Abstract The Hamming distance between two words of equal length is the number of positions where the two words differ. This distance is extended to a distance between words and languages and to a maximal distance of words of given length and a language. We investigate these distances between words and various sets of primitive words and various sets of periodic words which have been introduced in the paper Ito/Lischke: Generalized periodicity and primitivity for words, Math. Log. Quart. 53, 2007. The distance from an arbitrary word to one of the sets of primitive words is not greater than one. In the opposite direction, from primitive words to nonprimitive words this distance may be greater, and we determine it exactly to the periodic words and to the semi-periodic words, depending from the lengths of the words and from the cardinality of the alphabet.