Logik in der Informatik Prof. Dr. Nicole Schweikardt

In diesem Logbuch werden regelmäßig Informationen bereit gestellt. Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden.

1. Di, 15.04.2025:
   • Eröffnungsveranstaltung: Einführung ins Thema, Klärung von Organisatorischem (entlang der Webseite der Vorlesung). Abschnitt 1.1 (Wdh. Formale Sprache und reguläre Ausdrücke)
   Material:
   • Folien 1--21
   • Skript 1--15

2. Di, 22.04.2025:
   • Abschnitt 1.2 Begrifflichkeiten rund um endliche Automaten. Beginn mit dem Kapitel 2: Probleme endlicher Automaten auf endlichen Worten: Leerheitsproblem (inkl. Beweis), Wortproblem und Sprachendlichkeitsproblem (inkl. Beweisidee), Universalitätsproblem (inkl. Beweis Zugehörigkeit; Härtebeweis angefangen)

   Material:

   • Folien 22--38
   • Skript 15--27

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach [Link]

3. Fr, 25.04.2025:
   • Probleme endlicher Automaten auf endlichen Worten: Heute Abschluss Härtebeweis Universalität, Inklusions- und Äquivalenzproblem. Neuer Abschnitt: Logik und Automaten: Wiederholung Grundbegriffe Logik erster Stufe (speziell auf Wortstrukturen), Beweis (aa)+ ist nicht FO-defbar.

   Material:

   • Folien 38--58
   • Skript 27--40

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Henrik Björklund et al.: Logik und Automaten: ein echtes Dreamteam [Link]

4. Di, 06.05.2025:
   • Einführendes Beispiel für Intuition; MSO:Syntax und Semantik von MSO auf Wortstrukturen, BET-Theorem (Beweis -> LuK), Entscheidbarkeit von Erfüllbarkeitsproblem und Äquivalenzproblem auf Wortstrukturen mittels Automaten gezeigt, model checking problem, Zitat von Meyer & Stockmeyer, Syntax und Semantik SFR, Satz von McNaughton und Papert [Theorem 2.31] (Beweis -> LuK), nicht-zählende reguläre Sprachen; Erweiterung unseres Theorems 2.31 und Beweis (sternfrei regulär => nicht zählend)

   Material:

   • Folien 59--75
   • Skript 40--51

5. Fr, 09.05.2025:
   • Beweis LTL => FO, Sternhöhe (verallgemeinerter) regulärer Ausdrücke, Feedbackzahl endl. Automaten.
     Neuer Abschnitt: Minimierung von Automaten: NFA-Homomorphismen, Wdh. Äquivalenzrelationen und Partionierungen, Quotientenautomat, DFA-Homomorphismus, Kongruenz, Quotienten-DFA

   Material:

   • Folien 80--94
   • Skript 52--64

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • J.-É. Pin et al.: Some results on the generalized star-height problem [Link]

6. Di, 13.05.2025:
   • Beweis L(A) =L(A_/~A); Minimierung von DFA: Myhill-Nerode-Äquivalenz, kanonischer Automat, Beweis L=(A_L), Index eine ÄR, Zusammenhang zw. Index der Nerode-ÄR und regulären Sprachen, Isomorphie minimaler DFA, Algorithmus zur Berechnung der kan. Kongruenz; Beispiellauf des Algo.;

   Material:

   • Folien 95--107
   • Skript 64--74

7. Fr, 16.05.2025:
   • Minimierung von NFA: Minimierung als Entscheidungsproblem (inkl. Beweis PSPACE-Härte), Bisimulationsspiel und der dazugehörigen Quotientenautomat; Das syntaktische Monoid: Monoid(Def.), Homomorphismen über Monoiden, Satz (Zhg reguläre Sprachen und endl. Monoid, inkl. Beweis), Transitionsmonoid, das syntaktische Monoid in zwei äquivalenten Def. (inkl. Beweis der Äquivalenz)

   Material:

   • Folien 105--123
   • Skript 72--86

   Ergänzende Lektüre, in der Sie bei Interesse weiterlesen können (aber nicht müssen):

   • Berstel et al.: Minimization of Automata. [Link]

8. Di, 20.05.2025:
   • Gruppenfreiheit von Monoiden und der Satz von Schützenberger (ohne Beweis), Anwendungen am Bsp. sternfreier regulärer Sprachen
     Neuer Abschnitt: Alternierende Automaten, Def inkl positiv Boole'schen Formeln und deren Semantik, Lauf und Sprache von AFAs, Bsp. AFA als kompakte Repräsentanten reg. Sprachen. Dualer AFA. Satz und Beweis zu NFA -> AFA und AFA -> NFA, gedächtnislose Läufe von AFA.

   Material:

   • Folien 123--134
   • Skript 86--98

9. Fr, 23.05.2025:
   • Neuer Abschnitt: Lernen regulärer Sprachen: Angluin's scenario, erster naiver Ansatz, Angluin's Lernalgorithmus am Beispiel, dabei Definition des observation table, dessen Vollständigkeit und Konsistenz, Hypothese-DFA.
     Neuer Abschnitt: Automaten mit Ausgabe. Moore Automat, Mealy Automat und deren Äquivalenz (inkl. konstruktivem Beweis)
     

   Material:

   • Folien 134--146
   • Skript 98--112

10. Di, 27.05.2024:
    • Neues Kapitel: Endliche Automaten auf endlichen Bäumen. Abschnitt Bäume: Einführende Beispiele, Alphabet mit Rang, zwei äquivalente Def. von Σ-Bäumen; DbuTA, Akzeptanz und Sprache, Höhe von Σ-Bäumen, Beispiele für von einem DbuTA akzeptierte Baumsprachen, Def.: reguläre Baumsprachen; Zhg. Ableitungsbäume kontextfreier Grammatiken und reg. Baumsprachen; Abschlußeigenschaften reg. Baumsprachen; Bsp. einer nicht regulären Baumsprache; Pumping Lemma und Beispielanwendung; NbuTA; Ausdrucksstärke NbuTA vs. DbuTA;

    Material:

    • Folien 146--164
    • Skript 113--128