Wortersetzungssysteme

In dieser Veranstaltung werden die folgenden Themen behandelt werden:
  1. Wortersetzungssysteme als Darstellungen für Monoide und Gruppen.
  2. Unentscheidbarkeit des Wortproblems, der Konfluenz, der Termination etc.
  3. Entscheidbare Probleme für vollständige Wortersetzungssysteme und ihre Komplexität.
  4. Darstellung von Monoiden und Gruppen mittels vollständiger Wortersetzungssysteme.
Diese Veranstaltung richtet sich an Studenten mittlerer und höherer Semester. Grundkenntnisse über Berechenbarkeit und Automatentheorie oder die Bereitschaft, sich diese selbständig anzueignen, werden vorausgesetzt.

Literatur:

R.V. Book, F. Otto:
String-Rewriting Systems
Springer, New York, 1993.
M. Davis:
Computability and Unsolvability
McGraw-Hill, New York, 1958.
M. Jantzen:
Confluent String Rewriting
Springer, Berlin, 1988.
G. Lallement:
Semigroups and Combinatorial Applications
Wiley-Interscience, 1979.