Theoretische Informatik kurzgefasst

Das Buch macht den Leser in kompakter Form mit den wesentlichen Grundzügen der Theoretischen Informatik vertraut. Es führt in die Thematik Formale Sprachen, Grammatiken und Automaten ein. An eine Diskussion des Berechenbarkeitsbegriffs und unentscheidbarer Probleme schließt sich eine Einführung in die Komplexi-tätstheorie, speziell die Theorie der NP-Vollständigkeit, an. Querbezüge zwischen den Fachgebieten werden aufgezeigt. In der 3. Auflage wurden Erweiterungen eingearbeitet, wie zum Beispiel der Komplementabschluß der kontext-sensitiven Sprachen, die Greibach- und Kuroda-Normalform, weitere Unentscheidbarkeitsergebnisse für kontextfreie Sprachen, ein Beweis für die Äquivalenz von LOOP-Berechenbarkeit und primitiver Rekursivität, ein Hinweis auf das 10. Hilbertsche Problem, weitere NP-Vollständigkeitsresultate, sowie eine etwas anders gestaltete Darstellung der Ackermann-Funktion.