Theoretische Informatik

Lutz Priese: Studium der Mathematik an der Westfälischen Wilhelms-Universität Münster, Promotion 1974; Habilitation in Informatik 1979 an der Universität Dortmund; C3-Professor für Informatik an der Universität-Gesamthochschule Paderborn 1980 – 1991; seit 1991 C4-Professor für Theoretische Informatik an der Universität Koblenz-Landau, Gründungsleiter des Instituts für Computervisualistik, Gründung einer Firma zur industriellen Bildverarbeitung, 1. Innovationspreis des Landes Rheinland-Pfalz 2000.Katrin Erk: Studium der Informatik an der Universität Koblenz-Landau, Promotion an der Universität des Saarlandes 2002; wissenschaftliche Mitarbeiterin am Institut für Computerlinguistik, Universität des  Saarlandes 2002 – 2006; seit 2006 Professorin für Computerlinguistik an der University of Texas at Austin im Linguistics Department.

• Begriffe und Notationen.- Eine kurze Einführung in die Aussagenlogik.- Grammatiken und formale Sprachen.- Reguläre Sprachen und endliche Automaten.- Kontextfreie Sprachen.- Turing-Maschinen.- Die Sprachklassen ℒ, ℒ0 und ℒ1.- Abschlusseigenschaften von Sprachklassen.- Berechenbarkeit.- Registermaschinen.- Rekursive Funktionen.- Unentscheidbare Probleme.- Alternative Berechnungsmodelle.- Komplexität.