Berechenbarkeit Komplexität Logik: Algorithmen, Sprachen Und Kalküle Unter Besonderer Berücksichtigung Ihrer Komplexität

ISBN-13: 9783528289287 / Niemiecki / Miękka / 1992 / 499 str.

Egon B. Rger; Egon Borger

Opis

Endlich liegt der ,,Klassiker" der Theoretischen Informatik, der Studenten und Forschern ein unentbehrliches Standardwerk ist, in neuer Auflage vor.

Spis treści

Inhaltsübersicht.- Erstes Buch: Elementare Berechnungstheorie.- A: Mathematischer Algorithmusbegriff.- I Churchsche These.- § 1. Begriffsexplikation Umformungssystem, Rechensystem, Maschine (Syntax und Semantik von Programmen), Turingmaschine, strukturierte (Turing- und Registennaschinen-) Programme (TO, RO).- § 2. Äquivalensatz F??F (RO) ?F (TO)?F(TM), LOOP-Programm-Synthese für primitiv rekursive Funktionen, F (TM) ?F (RO) ?F?.- § 3. Exkurs über Semantik von Programmer Äquivalenz operationaler und denotationaler Semantik für RM-while-Programme, Fixpunktdeutung von Programmen, Beweis des Fixpunktsatzes.- § 4. Erweiterter Äquivalenzsatz simulation anderer Begriffs-explikationen: Modulare Maschinen, 2-Registermaschine, Thue-systeme, Markovalgorithmen, angeordnete Vektoradditionssysteme (Petrinetze), Postsche (kanonische bzw. reguläre) Kalküle, Wangsche nicht-löschende Halbbandmaschine, Wortregistermaschine.- § 5. These von Church.- II Universelle Programme und Rekurslonstheorem.- § 1. Universelle, Programme Kleene-Normalform, akzeptable universelle Programmiersysteme und effektive Programmtransformationen.- § 2. Diagonalisierungsmethode Rekursionstheorem: Fixpunktdeutung (Satz von Rice), Rekursionsdeutung (implizite Definition: rekursive Aufzählung von Fprim, injektive Übersetzungsfunktionen in Gödelnumerierungen, Isomorphiesatz für Gödelnumerierungen, sich selbst reproduzierende Programme), parametrische effektive Version mit unendlich vielen Fixpunkten.- B: Komplexität Algorithmischer Unlösbarkeit.- I Rekursiv Unlösbare Probleme (Reduktionsmethode).- § 1. Halteproblem K Spezialfälle des Satzes von Rice.- § 2. Einfache Reduktionen von K Entscheidungsprobleme berechnungs-universeller Systeme, Postsches Korrespondenzproblem, Dominoproblem, Röddingsches Wegeproblem.- * § 3. Exponentiell diophantische, Gleichungen simulation von RO.- * § 4. ? x, y, z.x=yz ist diophantisch Pell-Gleichungen.- II Arithmetische Hierarchie und Unlösbarkeitsgrade.- § 1. Rekursiv aufzählbare Prädikate Darstellungssätze, Universalität.- § 2. Arithmetische Hierarchie Aufzählungs- und Hierarchiesatz Darstellungssatz, Komplexitätsbestimmungen (Unendlichkeits-, Anzahlaussagen, arithmetischer Wahrheitsbegriff).- * § 3. Reduktionsbegriffe und Unlösbarkeitsgrade Reduktionsbegriffe (Satz von Post), Indexmengen (Satz von Rice & Shapiro, ?n -vollständige Programmeigenschaften), Kreativität und ?1-Vollständigkeit (Satz von Myhill), Einfache Mengen (?1. versus ?m versus ?tt, Satz von Decker und Yates), Prioritätsmethode (Satz von Friedberg & Muchnik), Komplexität des arithmetischen Wahrheitsbegriffs.- III Allgemeine Berechnungskomplexität.- § 1. Beschleunigungsphänomen Allg. Komplexitätsmaße, Blumscher Beschleunigungssatz, Unmöglichkeit effektiver Beschleunigung.- § 2. Beliebig komplizierte Funktionen Satz von Rabin-Blum-Meyer über Funktionen beliebig großer Programm- oder Rechenzeitkomplexität, Blumscher Programmverkürzungssatz, Lückensatz, Vereinigungssatz.- * § 3. Zerlrgungstheorie universeller Automaten Charakterisierung der Laufzeit-, Ein-, Ausgabe-, Übergangs- und Stopfunktionen universeller Automaten; Unmöglichkeit uniformer rekursiver Simulationsschranken bei universellen Automaten.- C: Rekursivität und Komplexität.- I Komplexitätsklassen Rekursiver Funktionen.- § 0. Das Modell der k-Band-Turingmaschine Bandreduktion, Band- und Zeitkompression, Simulationskomplexität eines universellen Programms.- § 1. Zeit- und Platzhierarchiesätze Satz von Fürer.- § 2. Komplexität nickt determinierter Programme Satz von savitch.- II Komplexitätsklassen Primitiv Rekursiver Funktionen.- § 1. Grzegorczyk-Hierarchiesatz Äquivalenz der Charakterisierungen durch Wachstum (beschränkte Rekursionen, Einsetzungen in Ackermannzweige), Rekursions- und Looptiefe, Rechenzeitkomplexität aus Kleene-Normalform mit polynomialbeschränkten bzw. R3-Kodierungsfunktionen.- * § 2. En-Basis- und En -Rechenzeithierarchiesatz.- * § 3. Ackermannfunktion und Goodstein-Folgen Satz von Goodstein & Kirby & Paris.- III Polynomial und Exponentiell Beschränkte Komplexitätsklassen.- § 1. NP-vollständige. Probleme. Halte-, Domino-, Partitions-, Rucksack-, Cliguen-, Handlungsreisenden- und ganz-zahliges Programmierungsproblem.- § 2. Vollständige Probleme für PBAND und exponentielle Klassen.- IV Endliche Automaten.- § 1. Charakterisierungen durch (in-) determinierte Akzeptoren und Akzeptoren und reguläre Ausdrücke Sätze von Rabin & Scott, Kleene.- § 2. Charakterisierung durch Kongruenzrelationen der Ununterscheid-barkeit Satz von Myhill & Nerode mit Korollaren (Zustands- minimalisierung, Beispiele nicht regulärer Sprachen, Schleifenlemma, 2-Weg-Automaten).- * § 3. Zerlegungssätze Produktzerlegung, Modulare Zerlegung (Röddingsche Normalform bei sequentieller und paralleler Signalverarbeitung).- * § 4. Kleine universelle Programme 2-dimensionale TM mit 2 Zuständen und 4 Buchstaben, 2-dimensionales Thuesystem mit 2 Regeln und 3 Buchstaben, PBAND-Vollständiges Schleifenproblem.- V; Kontextfreie Sprachen.- § 1. Normalformen von Chomsky- und Greibach, Herleitungbäume.- § 2. Periodizitätseigenschaften Schleifenlemma, Satz von Parikh, induktive Charakterisierung durch Substitutionsiteration.- § 3. Maschinencharakterisierung Kellerautomaten, Abschlußeigen Schäften.- § 4. Entscheidungsprobleme, Entscheidbarkeitssatz für kontextfreie und reguläre Grammatiken, Komplexität des Äquivalenzproblems regulärer Ausdrücke; Unentscheidbarkeitssatz für kontextfreie Grammatiken, Unmöglichkeit effektiver Minimalisierung.- * § 5. Abgrenzungen gegen Chomsky-Hierarchieklassen Durchschnitt regulärer mit Klammersprachen, L-R Herleitungsbeschränkung von Typ-O-Grammatiken, kontextabhängige Sprachen (Platzbedarfsatz und LBA-Problem).- Zweites Buch: Elementare Prädikatenlogik.- D: Logische Analyse Des Wahrheitsbegriffs.- I Syntax und Semantik.- § 1. Formale, Sprachen der 1. Stufe.- § 2. Interpretation formaler Sprachen.- § 3. Hilbert-Kalkül.- II Vollständigkeitssatz.- § 1. Herleitungen und Deduktionstheorem der Aussagenlogik.- § 2. Aussagenlogischer Vollständigkeitssatz (Lindenbaumscher Maximalisierungsprozeß; anaytische Tafeln, Resolution).- § 3. Herleitungen und Deduktionstheorem der Prädikatenlogik.- § 4. Prädikatenlogischer Vollständigkeitssatz.- III Folgerungen Aus Dem Vollständigkeitssatz.- § 1. Ausdrucksschwäche der PL 1 Satz von Skolem, Kompaktheits-satz, Nichtcharakterisierbarkeit des Endlichkeitsbegriffs, zahlentheoretische Nicht-Standard-Modelle.- * § 2. Prädikatenlogik der 2. stufe und Typentheorie Charakterisierung der Endlichkeit, der Abzählbarkeit und von (N;O,+1) in der 2. Stufe; Sprachen n-ter Stufe.- § 3. Kanonische Erfüllbarkeit Skolemsche Normalform, (minimale) Herbrand-Modelle, prädikatenlogische Resolution, prozedurals Interpretation von Hornformeln, Vollständigkeit der SLD-Resolution.- E: Logische Analyse Des Beweisbegriffs.- I: Gentzens Kalkül LK.- § 1. Der Kalkül LK (Klassische Logik).- § 2. Äquivalenz zum Hilbert-Kalkül.- * Teil II: Schnitteliminationssatz Für LK.- * Teil III: Folgerungen Aus Dem Schnitteliminationssatz.- § 1. Gentzens Hauptsatz (Kor: Satz von Herbrand).- § 2. Interpolatxonssatz Kor: Definierbarkeitssatz. Widerlegung von Interpolations- und Definierbarkeitssatz im Endlichen.- F: Komplexität Logischer Entscheidungsprobleme.- I: Unentscheidbarkeit & Reduktionsklassen.- § 1. Sätze von Church & Turing, Trachtenbrot, Aanderaa & Börger Kor: PROLOG-Programm als Axiom einer wesentlich unentscheid- baren Theorie bzw. erfüllbare Formel ohne rekursive Modelle, PROLOG-Definierbarkeit aller berechenbaren Funktionen, Unmöglichkeit rekursiver Interpolation und rekursiver Explikationsschranken impliziter Definitionen.- * § 2. Reduktionstyp von Kahr-Moore-Wang.- II: Unvollständigkeit Der Arithmetik.- Unvollständigkeitssatz von Gödel, Satz von Löb..- III: Rekursive Untere Komplexitätsschranken.- § 0. Reduktionsmethode.- § 1. Komplexität Boolescher Funktionen Satz von Cook, Satz von Henschen & Wos, polynomiale Äquivalenz von Horn- und Netzwerkkomplexität, Satz von Stockmeyer.- * § 2. Spektrumproblem Spektrumcharakterisierung der E3-Rechenzeithierarchie (Satz von Rödding & Schwichtenberg, Jones & Selman, Christen); Logische Charakterisierung von NP durch globale existentielle zweitstufige Prädikate (Satz von Fagin), von P durch PL1+LFP mit Ordnung (Satz von Immerman & Vardi), von PBAND durch PL2+TC (Satz von Immerman).- * § 3. Vollständige, Entscheidungsprobleme für polynomiale und exponentielle Komplexitätsklassen.- Satz von Lewis (NEXPZEIT-Vollständigkeit des Erfüllbarkeitsproblems der monadischen Gödel-Kalmar-Schütte-Klasse V?L2V?n Monad), Satz von Plaisted (EXPZEIT-Vollständigkeit des Erfüllbarkeitsproblems der Bernays-Schönfinkel-Klasse V?V? in Hornfomeln. Korollar: NEXPZEIT-Vollständigkeit für V?V?), Satz von Plaisted und Benenberg & Lewis (PBAND-Voll- ständigkeit des Erfüllbarkeitsproblems der Bernays-Schönfinkel- Klasse in Krom- (und Horn-)formein. Korollar: PBAND-Vollständigkeit von V?V? in determinierten Krom- und Hornformeln..- Bibliographie.- Symbolverzeichnis.

O autorze

Egon Börger ist Professor für Informatik an der Universität Pisa (Italien) und Alexander-von-Humboldt-Forschungspreisträger.