DEAs und NEAs
Pumping Lemma für reguläre Sprachen
Playlist (3 Videos)
Abschlusseigenschaften regulärer Sprachen
Playlist
Entscheidungsprobleme für reguläre Sprachen
Kontextfreie Sprachen und Kellerautomaten
Pumping Lemma für kontextfreie Sprachen
Playlist
Minimale DEAs
Turingmaschinen
Church-Turing-These, DTMs, NTMs, Mehrband-Maschinen
Unentscheidbarkeit
Kodierungen, unentscheidbare Probleme (Halteproblem, Leerheitsproblem, Wortproblem, Äquivalenzproblem), Satz von Rice, Busy Beaver, rekursive Aufzählbarkeit
Zeitkomplexität
P, NP, ExpTime, Polyzeit-Reduktionen
NP-Vollständigkeit
Satz von Cook/Levin, 3SAT, Vertex Cover, Clique, 3-Färbbarkeit, stark NP-vollständig, NP-Zertifikate
coNP
coNP-Vollständigkeit
LOOP- und WHILE-Programme
Unentscheidbarkeit in der
Chomsky-Hierarchie
Arithmetische Hierarchie
Wörter und formale Sprachen
Platzkomplexität
PSpace, Satz von Savitch
PSpace-Vollständigkeit
QBF, Geography
LogSpace und NLogSpace
Chomsky-Hierarchie
Chomsky-Normalform
Theorem von Chomsky und Schützenberger
Greibach-Normalform
CYK-Algorithmus
Playlist (2 Videos)
µ-rekursive und primitiv-rekursive Funktionen
Aussagenlogik
Syntax und Sematik, Normalformen, Erfüllbarkeit und Gültigkeit, funktionale Vollständigkeit
Logik erster Stufe
Motivation, Syntax und Semantik, Auswertung, Erfüllbarkeit, Ehrenfeucht-Fraïssé-Spiele, Sätze von Löwenheim-Skolem, Kompaktheitssatz

Kompaktheitssatz
Turingmaschinen vs. Grammatiken
NTMs und Typ-0-Sprachen, LBAs und Typ1-Sprachen
Kuroda-Normalform
Reguläre Ausdrücke
Playlist
Lemma von Arden
O-Notation
Playlist
SAT
SAT, 3SAT, Resolution, 2SAT, Horn-SAT, Markierungsalgorithmus
Unentscheidbare
Tiling-Probleme
Alternierung
Alternierende endliche Automaten
Unendliche Wörter
ω-Sprachen, Büchi-Automaten,
ω-reguläre Ausdrücke, Rabin-Automaten, Streett-Automaten, Muller-Automaten, Parity-Automaten
Fertige Serie
Legende
Alte Serie (wird irgendwann überarbeitet)
Laufende Serie (work in progress)
Geplante Serie
Modallogik
Determinisierung von Büchi-Automaten
Safra-Konstruktion
Aktualisiert: 09.08.2022
Schaltkreiskomplexität
Polynomialzeit-Hierarchie und Alternierung
Komplexität (fortgeschrittene Themen)
NP-Vollständigkeit, Satz von Ladner, Satz von Mahaney, Constrains Satisfaction Probleme, Platzkomplexität, Schaltkreiskomplexität, Polyzeit-Hierarchie, Alternierende Turingmaschinen, Satz von Baker, Gill, Solovay