Arbeitsgruppe
Grundlagen der Informatik
Prof. Dr. K. Madlener
|
Vorlesung Wortersetzungssysteme SS'98
|
Prof. Dr. K. Madlener
Betreuer: Dirk Zeckzer
Inhalt
Allgemeines,
Literatur,
Übungen.
Allgemeines
- 4 Std. Vorlesung
Mo. 08.00-09.30 Uhr, 46-260
Mi. 10.00-11.30 Uhr, 46-260
2 Std. Übung
Beginn: n.V. siehe Aushang
- A)
Wortersetzungssysteme bilden die Grundlage vieler algorithmischer Lösungen
für Probleme in algebraischen Strukturen, wie etwa in Monoiden, Gruppen und
Ringen. Sie sind somit wichtiger Bestandteil moderner Computer Algebra
Systeme. Ziel der Vorlesung ist es, die wichtigsten Eigenschaften von
Wortersetzungssystemen zur Darstellung algebraischer Strukturen zu
untersuchen, spezielle algorithmische Eigenschaften solcher Systeme, die
effiziente Lösungen ermöglichen, zu charakterisieren und ihre Integration
und Implementierung in existierenden CA-Systemen vorzustellen. Weiterhin
werden Eigenschaften spezieller konvergenter Wortersetzungssysteme
untersucht sowie wichtige Entscheidungsprobleme mit ihrer Komplexität
vorgestellt und die Ausdruckskraft, insbesondere die
Strukturierungsmöglichkeiten, näher studiert.
- B)
M. Jantzen: Confluent String Rewriting. Springer Verlag, 1988 EATCS
Mon. 14.
R. Book, F.Otto: String-Rewriting Systems. Springer Verlag, 1993 TMCS
- C)
Grundlagen der Informatik, wie sie etwa im Grundstudium durch die
Theorieveranstaltungen (Automatentheorie, Formale Sprachen und
Berechenbarkeit) vermittelt werden.
- D)
Schein für das Hauptstudium nach Bedarf.
- E)
Geeignet für Informatik- und Mathematikstudierende ab 4. Fachsemester.
Literatur
-
Allgemein und Übersichten:
-
Avenhaus:
Reduktionssysteme.
Springer Verlag, 1995.
-
R. Bündgen:
Termersetzungssysteme.
Vieweg Verlag, 1998.
-
R. Book, F.Otto:
String-Rewriting Systems.
Springer Verlag, 1993 TMCS
-
M. Jantzen:
Confluent String Rewriting.
Springer Verlag, 1988 EATCS Mon. 14.
-
Benninghofen, Kemmerich, Richter:
Systems of Reduction.
Springer Verlag, 1988.
-
Le Chenadec:
Canonical Forms in Finitely Presented Algebras.
Pitman Verlag, 1986.
-
Spezielle Literatur:
-
Andrea Sattler-Klein:
A Systematic Study of Infinite Canonical Systems generated by Knuth-Bendix Completion and Related Problems.
Dissertation, 1996.
-
RTA'97. Konferenz 1997.
-
C. Squier:
Word problems and a homological finiteness condition for monoids.
J. Pure Applied Algebra 49 (1987), 201-217.
-
Paliath Narendran,
Colm Ó'Dúnlaing:
Cancellativity in Finitely Presented Semigroups.
JSC 7(5): 457-472 (1989)
Übungen
