Diplomarbeit DIP-2328

Bibliograph.
Daten
Müller, Martin: Der polynomielle Abschluß von Sprachklassen über Spuren.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 2328 (2005).
53 Seiten, deutsch.
CR-Klassif.F.4.3 (Formal Languages)
KeywordsSpuren; Spurtheorie; Erkennbarkeit; polynomieller Abschluß; eindeutiger polynomieller Abschluß; eindeutiges Produkt; Varietäten; DA
Kurzfassung

Ein bedeutendes Resultat von Eilenberg zeigt die bijektive Korrespondenz von Varietäten endlicher Monoide und Varietäten von Sprachen. Ebenso wie bestimmte Operationen auf einzelnen Sprachen Entsprechungen auf ihren syntaktischen Monoiden haben, kann man die Frage nach algebraischen Entsprechungen von Operationen auf Varietäten von Sprachen stellen.

Zwei interessante Operationen auf Varietäten von Sprachen sind das Bilden von Polynomen als endliche Vereinigungen von Sprachen der Form L_0 a_1 L_1 ... a_n L_n, wobei die a_i einzelne Zeichen sind, und das Bilden von eindeutigen Polynomen, bei denen man zusätzlich fordert, daß jedes Wort aus der resultierenden Sprache genau eine passende Faktorisierung besitzt. Arbeiten von Schützenberger, Pin, Straubing und Thérien zeigten schließlich, daß der eindeutige polynomielle Abschluß als algebraische Entsprechung das Mal'cev-Produkt mit der Varietät LI hat. Pin und Weil konnten zeigen, daß auch der polynomielle Abschluß einem Mal'cev-Produkt entspricht, nämlich dem mit der Varietät geordneter Halbgruppen LJ+.

Wir stellen die erwähnten Ergebnisse über Wörtern und deren Beweise sowie die notwendigen Hintergründe vor. Soweit möglich, werden die Ergebnisse auf Spuren übertragen. Eine besondere Rolle wird hierbei der Varietät DA zukommen.

Volltext und
andere Links
PDF (1734114 Bytes)
Zugriff auf studentische Arbeiten aufgrund vorherrschender Datenschutzbestimmungen nur innerhalb der Fakultät möglich
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum21. Dezember 2005
   Publ. Informatik