Zur Startseite der Abteilung Theoretische Informatik

Automaten über unendlichen Wörtern (WS 2011/12)

Organisatorisches

  • Dozent: Dr. Manfred Kufleitner (Raum 1.160, Tel. 0711 / 685-88231, Sprechstunde nach Vereinbarung)
  • Vorlesungen: Do 15:45–17:15 in V38.03

Inhalt

  • Presburger Arithmetik: Anforderungen an Automaten
  • Büchi Automaten und omega-reguläre Sprachen
  • Andere Akzeptanzbedingungen für omega-Automaten
  • Monadische Logik zweiter Stufe (MSO)
  • Deterministische omega-Sprachen
  • Topologisch definierte Sprachklassen
  • McNaughtons Theorem
  • Die Safra-Konstruktion
  • Algebraische Beschreibungen
  • Eindeutige Büchi Automaten
  • Logik erster Stufe und andere Fragmente von MSO

Übungsblätter

Literatur

  • Olivier Carton und Max Michel: Unambiguous Büchi automata. Theoretical Computer Science 297 (2003) 37-81.
  • Volker Diekert und Paul Gastin: First-order definable languages. In Jörg Flum, Erich Grädel, Thomas Wilke (eds.). Logic and Automata: History and Perspectives. Texts in Logic and Games 2, Amsterdam University Press 2008, pp. 261-306.
  • Dominique Perrin und Jean-Eric Pin: Infinite words: Automata, semigroups, logic, and games Pure and applied mathematics series. Elsevier, 2004.
  • Wolfgang Thomas: Automata on infinite objects. In Jan van Leeuwen (ed.). Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics. Elsevier Science Publishers, Amsterdam, 1990, pp. 133-192.
  • Wolfgang Thomas: Languages, Automata, and Logic. In Grzegorz Rozenberg and Arto Salomaa. Handbook of Formal Languages, volume 3: Beyond Words. Springer, New York, 1997, pp. 389-455.