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--48
   • 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]