Automatentheorie und ihre Anwendungen, SoSe 2015, Universität Bremen

Automatentheorie und ihre Anwendungen, Sommersemester 2015

Vortragender: Dr. Thomas Schneider
Art der Veranstaltung: K4, Master-Ergänzung, „Spezielle Themen der Theoretischen Informatik“
Zeit und Ort: Di. 12–14, GW1-HS H1000
Mi. 8–10, SFG 2060 (Ausfall: 9.+10.6. – Ausweichtermin: 22.6. 16–18 Uhr, MZH 1380/1400)
siehe auch Eintrag im Vorlesungsverzeichnis Informatik fürs Sommersemester 2015
Erste Sitzung am Mi., 15.4., um 8:30 Uhr (GW1-HS H1000)

Kurzbeschreibung

Automatentheoretische Techniken haben nützliche Anwendungen in der Informatik: mit ihnen kann man beispielsweise sicherheitsrelevante Eigenschaften eines Systems überprüfen (Verifikation), robuste XML-Sprachen definieren oder Anfragen auf XML-Bäumen auswerten. Dazu muss man den Standard-Begriff von endlichen Automaten auf Wörtern verallgemeinern, indem man von endlichen Wörtern zu unendlichen Wörtern oder Bäumen übergeht. Diese Erweiterung des Automatenbegriffs sowie die damit verbundenen theoretischen Resultate und praktischen Anwendungen sind Gegenstand dieses Kurses.

Kurzübersicht der Themen:

Wiederholung von endlichen Automaten und formalen Sprachen
Automaten auf endlichen Bäumen
Automaten auf unendlichen Wörtern
(insbesondere Determinisierung)
Automaten auf unendlichen Bäumen
Anwendungen: Textsuche, Patternsuche, Textersetzung, XML-Schemasprachen, Verifikation und Temporallogik (LTL, CTL)

Wissen aus der Veranstaltung „Theoretische Informatik 1“ ist hilfreich, wird aber nicht vorausgesetzt – wir werden die wichtigsten Aspekte am Anfang kurz wiederholen.

Material

Themenübersicht als „Leitfaden“ fürs Fachgespräch

Folien

Einführung	4 pro Seite
Teil 1	4 pro Seite	(Version vom 22. 4., 15:30 Uhr)
Teil 2	4 pro Seite	(Version vom 12. 5., 19:15 Uhr)
Teil 3	4 pro Seite	(Version vom 24. 6., 16:20 Uhr)
Teil 4	4 pro Seite	(Version vom 14. 7., 15:10 Uhr)

Übungsblätter

Übungsblatt 1    (Abgabe am 28. 4.)
Übungsblatt 2    (Abgabe am 12. 5.)
Übungsblatt 3    (Abgabe am 26. 5.)
Übungsblatt 4    (Abgabe am 16. 6.)
Übungsblatt 5    (Abgabe am 30. 6.)
Übungsblatt 6    (Abgabe am 14. 7.)

Weiteres Material

kommentiertes Beispiel zur Safra-Konstruktion, Folien 60–63
Anmerkung zur Vergabe von Knotennamen bei der Safra-Konstruktion (korrigierte Fassung vom 22. 6.)

AG Theorie der künstlichen Intelligenz 15. 7. 2015 Thomas Schneider