The ambiguity of morphisms in free monoids and its impact on algorithmic properties of pattern languages

Abstract

Die vorliegende Arbeit untersucht eine fundamentale kombinatorische Ei- genschaft von Homomorphismen in freien Monoiden, nämlich ihre Mehrdeutigkeit. Dieser Begriff bezeichnet den Umstand, daß zu einem gegebenen Wort $α$und einem Homomorphismus $σ$durchaus ein zweiter Homomorphismus $τ$existieren kann, der $α$auf dasselbe Wort abbildet wie $σ$- es gilt also $σ(α) = τ(α)$, obwohl ein Symbol x in $α$existiert, für das sich $σ(x)$ von $τ(x)$ unterscheidet. Aufgrund ihres elementaren Charakters ist Mehrdeutigkeit von Homomorphismen eng verwoben mit einer Fülle von wichtigen Themen der Informatik. So stellt sie nicht nur die Grundlage des Postschen Korrespondenzproblems dar, sondern beeinflußt auch etliche Eigenschaften von Patternsprachen, welche insbesondere in der algorithmischen Lerntheorie von großer Bedeutung sind. Die kombinatorischen Hauptergebnisse der Arbeit - insbesondere zur Existenz von eindeutigen und sogenannten moderat mehrdeutigen Homomorphismen - erlauben daher diverse nichttriviale Rückschlüsse zu einigen klassischen Problemen für Patternsprachen.