Modulcode:	WI06
Englische Bezeichnung:	Applied automata theory
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	unregelmäßig
Präsenzzeiten:	4V 2Ü
ECTS:	7
Workload:	210 Std.
Dauer:	ein Semester
Modulkategorien:	WI (Sonstige)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Automaten gehören mit zu den grundlegenen Hilfsmitteln der Informatik; sie werden für die unterschiedlichsten Zwecke genutzt: zur Modellierung von Berechnungsmodellen, etwa in der Form von Transitionssystemen oder in der Form von so genannten Eingabe/Ausgabe-Automaten für die Modellierung verteilter Systeme; zur Ver- und Bearbeitung formaler Sprachen, etwa in Form von Kellerautomaten bei der Syntaxanalyse von Programmiersprachen oder in der Form von Baumautomaten bei der Bearbeitung von XML-Dokumenten; zur effektiven und effizienten Be- und Verarbeitung von Logiken und logischen Formalismen, etwa in der Form von Automaten auf unendlichen Wörtern bei der automatischen Verifikation von reaktiven Systemen oder bei der Konstruktion optimaler Entscheidungsprozeduren für die Presburger Arithmetik.

Lernziele:

Die erfolgreiche Benutzung von Automaten in der Informatik setzt ein Maß der Vertrautheit mit ihnen voraus, das über die in der entsprechenden Aufbaumodul gewonnene Erfahrung hinausgeht. Dies gilt insbesondere dann, wenn Automaten in (neuen) Anwendungsgebieten genutzt werden sollen. Dann müssen nämlich in der Regel geeignete Automatenmodelle selbst entworfen und Verfahren zum effizienten Umgang mit den jeweiligen Automaten selbst entwickelt oder zumindest bekannte angepasst werden. Entsprechende Techniken sollen den Studentinnen und Studenten vermittelt werden.

Lehrinhalte:

Es wird eine Auswahl getroffen an Automatenmodellen und Anwendungsgebieten, die zu dem oben beschriebene Lernziel passen. In Frage kommen zum Beispiel endliche Wortautomaten und pattern matching, Kellerautomaten und Syntaxanalyse, endliche Wortautomaten auf unendlichen Wörtern und Verifikation von Spezifikationen in temporaler Logik, endliche Wortautomaten und Presburger Arithmetik, endliche Baumautomaten und Typisierung für XML-Dokumente, probabilistische Automaten und Spracherkennung. Die Auswahl wird so getroffen, dass sowohl Modellierungsaspekte wie auch Effizienzfragen in angemessenem Umgang studiert werden können.

Weitere Voraussetzungen:

A3.4 und A4.1

Prüfungsleistung:

schriftliche Abschlussprüfung

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

ausgewählte wissenschaftliche Veröffentlichungen und Buchkapitel

Verweise:

Kommentar: