Definitionen

ε–Abschluss

Pumping-Lemma für reguläre Sprachen

Überflüssig

Zustandsäquivalenz

Der Äquivalenzklassenautomat

Zeugen für Nichtäquivalenz

Verallgemeinertes Pumping-Lemma

Rechtsinvarianz und Index

Nerode-Relation

berechenbar / totalrekursiv

Die universelle Turing-Maschine

Die Gödelnummer

Die Diagonalsprache

Halteproblem

Die Universelle Sprache

Eigenschaften von (semi-)entscheidbaren Sprachen

Problem, Kodierungsschema

NP-Vollständigkeit für Sprachen

NP-Vollständigkeit für Entscheidungsprobleme

Transitivität der poly. Transformation

Transitivität der poly. Transformation

Die Klassen co-P und co-N P

Aufzählungsprobleme

Pseudopolynomiale Algorithmen

Starke N P-Vollständigkeit

Approximationsalgorithmen

Absolute/Relative Approximationsalgorithmen

Genereller Ansatz

Bestmögliche Approximationsgüte

Approximationsschemata

DTAPE(s(n))

NTAPE(s(n))

Links/Rechtsableitung, Eindeutigkeit

Chomsky-Normalform

Der CYK-Algorithmus

Das Pumping-Lemma für kontextfreie Sprachen

Ogden’s Lemma für kontextfreie Sprachen

Nutzlose Variablen

Kellerautomaten

Sprache der korrekten Rechenwege