Automatentheorie und Logik 2002

Auf dieser Seite

• Termine
• Inhalt
• Literatur

 
 

Termine

Automatentheorie und Logik

Form: 4 Stunden Vorlesung (E. Best) und 2 Stunden Übung (H. Wimmel) pro Woche; mündliche Prüfung (Fachgespräch) oder Klausur.

Vorlesung: Mittwoch 8:00 - 10:00 A10 Hörsaal F.

           Donnerstag 8:00 - 10:00 A10 Hörsaal F.

Übung: Mittwoch 14:00 - 16:00 A7 0-025.

Erste Vorlesung: Mittowch, 10.4.2002.

Erste Übung: Dienstag, 16.4.2002.

Credits: 9.

Diese Vorlesung kann von Studierenden nach DPO-3 als Stammvorlesung gehört werden (6 SWS). Sie kann von DPO-4-Studierenden als Modul verwendet oder mit einer anderen (nicht notwendigerweise inhaltlich verwandten) Stammvorlesung zu insgesamt 3 Modulen kombiniert werden. Als Voraussetzung werden Kenntnisse in Automatentheorie, formalen Sprachen, Logik und Diskreter Mathematik im Umfang des Grundstudiums benötigt.

 

Inhalt

Der Satz von Büchi (1962) verknüpft endliche Automaten (und damit auch reguläre Sprachen) mit einer speziellen Logik, der monadischen Logik 2. Stufe. Büchis Satz hat zu vielfältigen Erweiterungen dieser Verknüpfung zwischen Automatentheorie und Logik Anlass gegeben. Stichpunkte sind hierbei:

• unendliche Wörter;
• Spiele;
• Halbgruppen und Monoide;
• Transitionssysteme;
• temporale und modale Logiken;
• Petrinetze;
• und Model-Checking (eine der praktisch relevanten Anwendungen).

In der Vorlesung wird die Theorie bis hin zu den Anwendungen präsentiert. Es werden viele Beispiele gegeben, um so das Verständnis von Konzepten zu erleichtern. Von den Beweisen werden vor allem solche ausführlich behandelt, die zu algorithmischen Anwendungen führen. Die Vorlesung wird durch wöchentliche Übungen vertieft.

 

Literatur

Ein Skriptum (z.Zt. 137 Seiten) befindet sich auf der folgenden Seite: http://theoretica.Informatik.Uni-Oldenburg.DE/~best/lecture-notes.html In diesem Skriptum finden sich weitere Literaturangaben.