Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik der Ludwig-Maximilians-Universität München

Vorlesung im Hauptstudium (SS 08):

Automatentheorie (V4Ü2)

Prof. Dr. M. Hofmann, Priv.-Doz. Dr. M. Lange, H. Gruber

Inhaltsverzeichnis dieser Seite

Inhalt

Aktuelles

Die Vorlesung am Mittwoch, 16.7.08, fällt aus.
Die Übung am Freitag, 11.7.08, fällt aus. Am 4.7.08 wurde kein Übungsblatt ausgeteilt. Das letzte Übungsblatt wird am 11.7.08 ausgeteilt und am 18.7.08 behandelt.
Die nächste Übung findet am Freitag, 9.Mai statt. Gemäß Wunsch des Teilnehmerkreises findet ab 9. Mai bis 4.Juli die Übung immer freitags, 12-14 Uhr c.t. im Hörsaal 1.31, in der Oettingenstrasse statt. Der Termin und Ort für die letzten beiden Übungen stehen noch nicht fest; voraussichtlich ist der Zeitpunkt aber ebenfalls jeweils Freitag, 12-14 Uhr c.t. Stay tuned!

Zeit Ort Beginn/Ende Veranstalter

Vorlesung: Mi 12-14 Oet 0.33 16.4. Hofmann/Lange

Do 14-16 Oet 1.39 Hofmann/Lange

Übung: Mo 10-12 Oet .15 21.4. bis 5.5. Gruber

Fr 12-14 Oet 1.31 9.5. bis 4.7.

Skript:

	Zeit	Ort	Beginn/Ende	Veranstalter
Vorlesung:	Mi 12-14	Oet 0.33	16.4.	Hofmann/Lange
	Do 14-16	Oet 1.39		Hofmann/Lange
Übung:	Mo 10-12	Oet .15	21.4. bis 5.5.	Gruber
Fr 12-14	Oet 1.31	9.5. bis 4.7.

Es kann leider keine Garantie auf Richtigkeit oder Vollständigkeit gegeben werden.

Hinweise auf Fehler im Skript nehmen wir natürlich gerne entgegen.

Übungsblätter:

Blatt 1 (pdf)
Blatt 2 (pdf)
Blatt 3 (pdf) Lösungsvorschläge Aufgabe 12 von Harald Zauner und Aufgabe 13
Blatt 4 (pdf)
Blatt 5 (pdf)
Blatt 6 (pdf)
Blatt 7 (pdf) Die Software fuer die Safra-Konstruktion gibt es hier (i386 binary, Linux) und eine Kurzanleitung hier.
Blatt 8 (pdf)
Blatt 9 (pdf)
Blatt 10 (pdf)
Blatt 11 (pdf)
Blatt 12 (pdf)
Blatt 13 (pdf)

Zuordnung:

Vorkenntnisse:

Vordiplom

Hörerkreis:

Studierende der Informatik im Hauptstudium

Studierende mit Nebenfach Informatik

Schein:

Schein gilt für Diplomprüfung in Haupt- und Nebenfach Informatik

zurück zum Inhaltsverzeichnis dieser Seite

Inhalt

Diese Vorlesung zeigt, wie Automaten benutzt werden können, um Entscheidungsverfahren für verschiedene Logiken zu erhalten.

Automaten auf endlichen Wörtern, Monadische Logik 2. Stufe, Satz von Elgot-Büchi, Presburger Arithmetik
Automaten auf unendlichen Wörtern, LTL
Automaten auf endlichen Bäumen, XML
Automaten auf unendlichen Bäumen, Satz von Rabin, modaler mu-Kalkül

Material

Mona-Dateien aus der Vorlesung vom 24.04.08
Das auf LTL basierende Werkzeug SMV .

Literatur

Aktuelle Übersichts- und Forschungsarbeiten, die in der Vorlesung bekannt gegeben werden.
F. Baader, Automatentheorie, Mitschrift einer Vorlesung, erhältlich auf Webseiten der TU Dresden.
W. Thomas, Languages, Automata, and Logic, Technical Report #9607, Institut für Informatik und Praktische Mathematik, CAU Kiel, 1996
E. Grädel, W. Thomas, Th. Wilke, Automata, Logics, and Infinite Games: A Guide to Current Research, Lecture Notes in Computer Science, volume 2500, Springer Verlag, 2002
M. Vardi, Alternating Automata and Program Verification, Lecture Notes in Computer Science, Volume 1000, Springer Verlag, erhältlich von M. Vardi's homepage.
J. E. Hopcroft, R. Motwani Rotwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computability, 2nd Edition, Addison-Wesley
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi, Tree Automata Techniques and Applications, erhältlich von http://www.grappa.univ-lille3.fr/tata/.
F. Neven, Automata, Logic, and XML, erhältlich von F. Neven's homepage.
F. Neven, Th. Schwentick, Query Automata, erhältlich von F. Neven's homepage.