Modelle und Konstruktionen der Automatentheorie
» This course is given in German.
Vorlesung im Sommersemester 2000
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| V4 | Di 08:15 - 09:45 AH I Do 08:15 - 09:45 AH VI |
11.04.2000 | Thomas |
| Ü2 | Di 14:00 - 15:30 AH V |
Inhalt
Ziel dieser Vorlesung ist es, eine kohärente Zusammenschau der vielen Automatenmodelle zu entwickeln, die man überall in der Informatik findet, z.B. endliche Akzeptoren, sequentielle Übersetzer, Kellerautomaten, Baumautomaten, Petrinetze. Ein Schwerpunkt wird die Behandlung algorithmischer Fragen über das Verhalten der Automaten (auch unendlicher Transitions-Systemen) sein. Zu den Anwendungen zählt u.a. die Programmverifikation und -synthese. Die Teilnahme an den Übungen wird dringend empfohlen. Die Vorlesung gehört zum Prüfungsbereich Theoretische Informatik des Informatik-Hauptstudiums. Sie kann auch im Bereich Angewandte Mathematik der Lehramtsprüfung Mathematik gewählt werden.
Inhaltsübersicht
- Automaten über Wörtern und Bäumen
- Minimierungsverfahren und Anwendungen
- Nichtdeterministische Automaten und reguläre Ausdrücke
- Hierarchische Automatenmodelle
- Automatendefinierbare Relationen
- Reguläre Repräsentationen kontextfreier Sprachen
- Transitionssysteme und Prozeß-Definitionen (u.a. Petrinetze)
- Bisimulation und zugehörige Entscheidungsprobleme
Zuordnung
Theoretische Informatik, Mathematik
Voraussetzungen
Vordiplom (Theor. Informatik) oder Vordiplom Mathematik
Sonstiges
Ein Skript (aus dem Sommersemester 1999) steht zur Verfügung. Allerdings wird die Vorlesung an einigen Stellen modifiziert; so wird der Abschnitt über Logik und Model-Checking durch ein Kapitel über hierarchische Transitionsmodelle ersetzt.