Sachgebiete

Beschreibung:

IX, 461 S. : graph. Darst. kart.

Bemerkung:

Der Einband ist leicht berieben, ansonsten ein sehr gutes und sauberes Exemplar ohne Anstreichungen. - INHALT - Kapitel 1 Vorbemerkungen - 1.1 Zeichenketten, Alphabete und Sprachen. - 1.2 Graphen und Bäume - 1.3 Induktionsbeweise - 1.4 Mengen-Notation - 1.5 Relationen. - 1.6 Übersicht über das Buch. - Kapitel 2 Endliche Automaten und reguläre Ausdrücke - 2.1 Systeme mit endlicher Zustandsmenge - 2.2 Grundlegende Definitionen - 2.3 Nichtdeterministische endliche Automaten - 2.4 Endliche Automaten mit e-Bewegungen - 2.5 Reguläre Ausdrücke - 2.6 Zweiseitige endliche Automaten. - 2.7 Endliche Automaten mit Ausgabe - 2.8 Anwendungen für endliche Automaten - Kapitel 3 Eigenschaften von regulären Mengen - 3.1 Das Pumping-Lemma für reguläre Mengen - 3.2 Abgeschlossenheit regulärer Mengen - 3.3 Entscheidungsalgorithmen für reguläre Mengen. - 3.4 Der Satz von Myhill-Nerode und die Minimierung endlicher Automaten - Kapitel 4 Kontextfreie Grammatiken - 4.1 Motivation und Einleitung - 4.2 Kontextfreie Grammatiken - 4.3 Ableitungsbäume. - 4.4 Vereinfachung kontextfreier Grammatiken. - 4.5 Chomsky-Normalform - 4.6 Greibach-Normalform - 4.7 Die Existenz inhärent mehrdeutiger kontextfreier Sprachen - Kapitel 5 Kellerautomaten - 5.1 Informelle Beschreibung - 5.2 Definitionen - 5.3 Kellerautomaten und kontextfreie Sprachen - Kapitel 6 Eigenschaften kontextfreier Sprachen - 6.1 Das Pumping-Lemma für kfS - 6.2 Abgeschlossenheit bei kfS - 6.3 Entscheidungsalgorithmen für kfS. - Kapitel 7 Turing-Maschinen - 7.1 Einführung. - 7.2 Das Turing-Maschinen-Modell - 7.3 Berechenbare Sprachen und Funktionen. - 7.4 Techniken zur Konstruktion von Turing-Maschinen. - 7.5 Modifizierte Turing-Maschinen - 7.6 Die Church'sche Hypothese. - 7.7 Turing-Maschinen als Generatoren - 7.8 Beschränkte, zum Grundmodell äquivalente Turing-Maschinen - Kapitel 8 Unentscheidbarkeit - 8.1 Probleme. - 8.2 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen.. - 8.3 Universelle Turing-Maschinen und ein unentscheidbares Problem. - 8.4 Der Satz von Rice und weitere unentscheidbare Probleme.. - 8.5 Unentscheidbarkeit des Post'schen Korrespondenzproblems. - 8.6 Gültige und ungültige Berechnungen von TM: ein Werkzeug zum Beweis für die Unentscheidbarkeit von kfS-Problemen - 8.7 Der Satz von Greibach - 8.8 Einführung in die Theorie rekursiver Funktionen - 8.9 Orakel-Berechnungen - Kapitel 9 Die Chomsky-Hierarchie - 9.1 Reguläre Grammatiken - 9.2 Nicht eingeschränkte Grammatiken - 9.3 Kontextsensitive Sprachen - 9.4 Relationen zwischen Sprachklassen. - Kapitel 10 Deterministische kontextfreie Sprachen - 10.1 Normalformen für DKA - 10.2 Abgeschlossenheit von dkfS unter Komplementbildung - 10.3 Vorhersagende Maschinen - 10.4 Zusätzliche Abgeschlossenheitseigenschaften von dkfS - 10.5 Entscheidbarkeitseigenschaften von dkfS - 10.6 LR(0)-Grammatiken - 10.7 LR(0)-Grammatiken und DKA - 10.8 LR(k)-Grammatiken - Kapitel 11 Abgeschlossenheitseigenschaften von Sprachfamilien - 11.1 Trios und volle Trios - 11.2 Abbildungen verallgemeinerter sequentieller Maschinen. 11.3 Weitere Abgeschlossenheitseigenschaften von Trios. - 11.4 Abstrakte Sprachfamilien. - 11.5 Unabhängigkeit der ASF-Operationen - 11.6 Zusammenfassung. - Kapitel 12 Komplexitätstheorie - 12.1 Definitionen. - 12.2 Lineare Beschleunigung, Bandkompression und Reduktion der Anzahl der Bänder. - 12.3 Hierarchie-Sätze. - 12.4 Beziehungen zwischen Komplexitätsmaßen. - 12.5 Translationslemmata und nichtdeterministische Hierarchien - 12.6 Eigenschaften allgemeiner Komplexitätsmaße: Der Lücken-, Beschleunigungs- und Vereinigungssatz - 12.7 Axiomatische Komplexitätstheorie - Kapitel 13 Hartnäckige Probleme - 13.1 Polynomiale Zeit und polynomiales Band - 13.2 Einige NP-vollständige Probleme - 13.3 Die Klasse Co-NP. - 13.4 PBAND-vollständige Probleme - 13.5 Vollständige Probleme für P und NBAND (log n). - 13.6 Einige beweisbar hartnäckige Probleme - 13.7 Die PNP Frage für TM mit Orakeln: Die Grenzen unserer Fähigkeit zu bestimmen, ob P = NP gilt - Kapitel 14 Wesentliche Aspekte anderer wichtiger Sprachklassen - 14.1 Hilfskellerautomaten. - 14.2 Stack-Automaten - 14.3 Indizierte Sprachen. - 14.4 Entwicklungssysteme - 14.5 Zusammenfassung. - Literatur - Index. ISBN 9783893197446