Die Vorlesung Automatentheorie und ihre Anwendungen (ATA) ist in zwei Teile ATA 1 und ATA 2 aufgeteilt. ATA 1 wird in der ersten Semesterhälfte von Prof. Neider gelesen, ATA 2 in der zweiten Hälfte von Prof. Jung. Beide Vorlesungen sind 2V+2Ü und ergeben also 6 ECTS, finden allerdings als 4+2 statt, da sie jeweils nur ein halbes Semester laufen. ATA 1 ist keine Voraussetzung für ATA 2 (aber natürlich ist es sinnvoll beide zu besuchen).

ATA 2 startet am 05.12.2023.

Weitere Informationen finden Sie zu gegebener Zeit im Moodle Raum. Registrierung via LSF.

Automatentheorie ist ein klassisches Teilgebiet der Theoretischen Informatik mit Anwendungen in vielen Bereichen der Informatik wie Verifikation, Logik, Datenbanken, usw. Die Vorlesungen ATA 1 und ATA 2 sollen einen Überblick über die wichtigsten Themen der Automatentheorie geben. Spezifisch wird sich ATA 1 mit Automaten auf endlichen Wörtern/Bäumen befassen und ATA 2 mit Automaten auf unendlichen Wörtern/Bäumen.

Dabei werden in ATA 1 insbesondere die folgenden Lerninhalte behandelt:

• Verschiedene Typen von Automaten über endlichen Wörtern
• Verschiedene Typen von Automaten über endlichen Bäumen
• Das Lernen endlicher Automaten
• Der Zusammenhang von Automaten und monadischer Logik zweiter Stufe
• Anwendungen (z. B. Model-Checking)

In ATA 2 werden die folgenden Lerninhalte behandelt:

• Verschiedene Typen von Automaten über unendlichen Wörtern
• Verschiedene Typen von Automaten über unendlichen Bäumen
• Abschlusseigenschaften und Umwandlungen zwischen verschiedenen Automatenmodellen
• Entscheidungsprobleme wie z.B. Leerheits-, Wort-, Äquivalenzproblem
• Anwendungen (z.B. Beziehung zu temporalen Logiken wie LTL und CTL, Model-Checking)