Algorithmische Modelltheorie: Vorlesung (Mo, 06.01.2020)
  • Einbetten

Kapitel:

00:00:08
Wiederholung (k-Bijektionsspiel)
00:18:08
CFI-Konstruktion
00:40:29
Satz (Charakterisierung der CFI-Graphen)
00:44:45
Lemma (lokale Charakterisierung bei gemeinsamen Knoten)
00:59:30
Lemma (einzelne Kanten)
01:04:20
Beweis (Charakterisierung der CFI-Graphen)
01:19:00
Satz (CFI-query ist in PTIME)
01:29:32
Ausblick (CFI-query ist nicht FPC-definierbar)