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. Fr, 19.04.2024:
   • Eröffnungsveranstaltung. 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, 23.04.2024:
   • 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)

   Material:

   • Folien 22--39
   • Skript 15--28

   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, 26.04.2024:
   • Probleme endlicher Automaten auf endlichen Worten: Heute Inklusions- und Äquivalenzproblem. Neuer Abschnitt: Logik und Automaten: Wiederholung Grundbegriffe Logik erster Stufe (speziell auf Wortstrukturen),Beweis (aa)+ ist nicht FO-defbar, einführendes Beispiel für Intuition MSO.

   Material:

   • Folien 40--60
   • Skript 29--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. Fr, 03.05.2024:
   • 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] (Bweis -> LuK), nicht-zählende reguläre Sprachen, sowie Syntax und Semantik von LTL auf Wortstrukturen inkl. Erweiterung unseres Theorems 2.31 und Beweis (sternfrei regulär => nicht zählend)

   Material:

   • Folien 61--80
   • Skript 41--52

5. Di, 07.05.2024:
   • 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]