Logo des Repositoriums
 
Textdokument

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

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2007

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik

Zusammenfassung

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.

Beschreibung

Reidenbach, Daniel (2007): The ambiguity of morphisms in free monoids and its impact on algorithmic properties of pattern languages. Ausgezeichnete Informatikdissertationen 2006. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-411-0. pp. 159-168

Schlagwörter

Zitierform

DOI

Tags