EN | DE
Theoretische Informatik

Algebraische und logische Aspekte der Automatentheorie

Automata 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 wichtige Querverbindungen zwischen der Automatentheorie und Gebieten der Mathematik (Algebra, Topologie und Logik) hergestellt.

Slogan (Marshall Stone): "Always topologize!"

Inhalt

  • 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

Literatur

  • 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