Zur Startseite der Abteilung Theoretische Informatik

Automaten über unendlichen Objekten (SS 2014)

Organisatorisches

  • Dozenten:
    Manfred Kufleitner (Raum 1.160, Tel. 0711 / 685 88231)
    Volker Diekert (Raum 1.125, Tel. 0711 / 685 88329)

  • Vorlesungstermine:
    ZeitRaumTermine Vorlesung
    Mo 11:30–13:00 0.108 wöchentlich
    Fr 11:30–13:00 0.108 vierzehntäglich im Wechsel mit der Übung

    Bitte beachten Sie kurzfristige Termin- und Raumänderungen, die an dieser Stelle veröffentlicht werden.


  • Übungstermine:
    ZeitRaumTermine Übungen
    Fr 11:30–13:00 0.108 vierzehntäglich mit der Vorlesung im Wechsel
  • Die Übungen am 23.05. finden um 14:00 Uhr im Raum 0.363 statt.

Vorlesungsmitschrieb

  • 07.04.2014: Presburger Arithmetik [PDF1] [PDF2] [PDF3]
  • 11.04.2014: unendliche Wörter, Büchi-Automaten, deterministische Büchi-Automaten, Vereinigung und Durchschnitt [PDF1] [PDF2] [PDF3] [PDF4] [PDF5]
  • 14.04.2014: omega-rationale Sprachen, der Satz von Ramsey, Erkennbarkeit, syntaktische Kongruenz nach Arnold [PDF1] [PDF2] [PDF3] [PDF4] [PDF5] [PDF6] [PDF7]
  • 25.04.2014: Komplementabschluss und syntaktische Monoide [PDF1] [PDF2] [PDF3] [PDF4]
  • 28.04.2014: keine Vorlesung
  • 02.05.2014: Äquivalente Charakterisierungen der Erkennbarkeit, Entscheidungsprobleme für Büchi-Automaten [PDF1] [PDF2] [PDF3] [PDF4] [PDF5] [PDF6] [PDF7]
  • 05.05.2014: MSO-Logik: von Automaten zu Formeln [PDF]
  • 09.05.2014: MSO-Logik: von Formeln zu Automaten, andere Automatenmodelle für omega-reguläre Sprachen [PDF1] [PDF2]
  • 12.05.2014: weitere Automatenmodelle, Umwandlungen zwischen den Automatenmodellen, Safra-Konstruktion (Teil 1) [PDF1] [PDF2] [PDF3] [PDF4]
  • 16.05.2014: Safra-Konstruktion (Teil 2), von deterministischen Muller-Automaten zu deterministischen Rabin-Automaten (Teil 1) [PDF1] [PDF1-Nachtrag] [PDF2] [PDF3]
  • 19.05.2014: von deterministischen Muller-Automaten zu deterministischen Rabin-Automaten und zu deterministische Parity-Automaten (Teil 2), untere Schranke für Büchi-Komplementierung nach Max Michel, von Streett-Automaten zu Büchi-Automaten, untere Schranke für Safra-Konstruktion [PDF1] [PDF2] [PDF3]
  • 23.05.2014: Klarlunds Konstruktion (Teil 1), Ordinalzahlen, Berechnungsgraph [PDF1] [PDF2] [PDF3] [PDF4]
  • 26.05.2014: Klarlunds Konstruktion (Teil 2), Korrektheit von Klarlunds Konstruktion ohne Auswahlaxiom [PDF1] [PDF2]
  • 30.05.2014: Pfeilsprachen, omega-reguläre Sprachen sind Boolesche Kombinationen von deterministischen Sprachen, weak-MSO-Logik, der Satz von Landweber über deterministische Sprachen [PDF1] [PDF2]
  • 02.06.2014: Cantor-Topologie, deterministische Sprachen und Borel-Hierarchie, offene omega-reguläre Sprachen [PDF1] [PDF2] [PDF3]
  • 06.06.2014: keine Vorlesung
  • 16.06.2014: Schwache Akzeptanzbedingungen [PDF]
  • 20.06.2014: Staiger-Wagner-Automaten, Carton-Michel-Automaten (Teil 1) [PDF1] [PDF2] [PDF3] [PDF4] [PDF5]
  • 23.06.2014: Carton-Michel-Automaten (Teil 2) [PDF1] [PDF2]
  • 27.06.2014: Topologischer Abschluss, Kompaktheit der Cantor-Topologie [PDF]
  • 30.06.2014: Monitorability [PDF]
  • 04.07.2014: Linear Temporal Logic (LTL): Syntax und Semantik [PDF]
  • 07.07.2014: Aperiodische Monoide, lokale Divisoren, von aperiodisch zu LTL (Teil 1) [PDF1] [PDF2] [PDF3]
  • 11.07.2014: Von aperiodisch zu LTL (Teil 2) [PDF]
  • 14.07.2014: Von LTL zu FO3, von FO zu sternfrei, von sternfrei zu aperiodisch [PDF1] [PDF2] [PDF3] [PDF4] [PDF5]

Übungsblätter

  • Blatt 1 (PDF, Besprechung am 25.04. um 14:00 Uhr im Raum 0.363)
  • Blatt 2 (PDF, Besprechung am 9.05. um 14:45 Uhr im Raum 0.363)
  • Blatt 3 (PDF, Besprechung am 23.05. um 14:00 Uhr im Raum 0.363)
  • Ideen für kleine Forschungsprojekte
  • Wir treffen uns am 18.07.2014 um 11:30 Uhr im Raum 0.108.

Materialien

  • Skript zur Vorlesung Automaten über unendlichen Wörtern vom Wintersemester 2011/2012 [PDF]

Literatur