Diploma Thesis DIP-2328

BibliographyMüller, Martin: Der polynomielle Abschluß von Sprachklassen über Spuren.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2328 (2005).
53 pages, german.
CR-SchemaF.4.3 (Formal Languages)
KeywordsSpuren; Spurtheorie; Erkennbarkeit; polynomieller Abschluß; eindeutiger polynomieller Abschluß; eindeutiges Produkt; Varietäten; DA
Abstract

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.

Full text and
other links
PDF (1734114 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateDecember 21, 2005
   Publ. Computer Science