Algebraische und logische Aspekte der Automatentheorie ws18

Dozent Dr. Henning Urbat
Umfang Vorlesung + Übung, 4 SWS, ECTS-Credits: 7,5
Zeit und Ort Mo, 10:15-11:45 Uhr, 01.255-128 und Mi, 12:15-13:45 Uhr, 01.255-128
Zielgruppe Informatik BSc (ab 5. Semester), Informatik MSc, Mathematik

Die erste Vorlesung findet am 15.10.2018 statt.

Inhalt der Vorlesung

Automaten als mathematische Formalisierung zustandsbasierter Systeme gehören zu den wichtigsten Werkzeugen der Theoretischen Informatik und besitzen zahlreiche Anwendungen, von der Compilerentwicklung bis zur Verifikation reaktiver Systeme. In dieser Veranstaltung, die an die Anfängervorlesungen des Informatikstudiums anknüpft, werden Querverbindungen zwischen der Automatentheorie und Gebieten der Mathematik (Algebra, Topologie und Logik) hergestellt:

Automata
  • Erkennung von regulären Sprachen durch Monoide und Halbgruppen
  • Proendliche Gleichungen und Varietäten von Sprachen
  • Logische Beschreibung regulärer Sprachen, Ehrenfeucht-Fraïssé-Spiele
  • Automaten, Algebra und Logik auf unendlichen Wörtern und Bäumen

Slogan (Marshall Stone): “Always topologize!”

Literatur

  • J.-E. Pin: Mathematical Foundations of Automata Theory
  • D. Perrin, J.-E. Pin: Infinite Words, Academic Press, 2004
  • H. Straubing: Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, 1994
  • E. Grädel, W. Thomas, T. Wilke: Automata, Logic, and Infinite Games, Springer, 2002

Übungsblätter

… gibt es in der StudOn-Gruppe zu dieser Lehrveranstaltung.