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

Vorlesung im Hauptstudium (SS 06):

Automatentheorie (V4Ü2)

Das Skript ist auf Anfrage (per Email) bei Martin Lange erhältlich.
Die Scheine liegen im Sekretariat (Zimmer Z1.05) zur Abholung bereit.
Die Übung am Donnerstag, 27.7.06, wird vorverlegt auf den Vorlesungstermin am Mittwoch, 26.7.06. Somit findet die letzte Vorlesung am Montag, 24.7.06, statt.
Fehlendes Stueck im Beweis, dass FOL-definierbare Sprachen sternfrei sind.
Hörsaaländerung: Ab sofort findet die Vorlesung montags im Raum 0.13 statt.
In Aufgabe 7d des Übungsblatts 1 hat sich ein Schreibfehler eingeschlichen. Es muss heissen: ... folgt jeweils a_{(i+1) mod n}.

Zeit Ort Beginn Veranstalter

Vorlesung: Mo 12-14 Oet 0.13 24.4. Hofmann/Lange

Mi 12-14 Oet 1.15 Hofmann/Lange

Übung: Do 12-14 Oet 0.15 27.4. Lange
Zuordnung:: T
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

	Zeit	Ort	Beginn	Veranstalter
Vorlesung:	Mo 12-14	Oet 0.13	24.4.	Hofmann/Lange
	Mi 12-14	Oet 1.15		Hofmann/Lange
Übung:	Do 12-14	Oet 0.15	27.4.	Lange

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

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.