Automatische Synthese rekursiver Programme als Beweisverfahren
著者
書誌事項
Automatische Synthese rekursiver Programme als Beweisverfahren
（Informatik-Fachberichte, 302）
Springer-Verlag, c1992
- : us
- : gw
大学図書館所蔵 件 / 全1件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
内容説明・目次
内容説明
In diesem Buch wird ein Verfahren vorgestellt, mit dem Induktionsbeweise vonExistenzaussagen automatisch gef}hrt werden k|nnen. Es ist ein deduktives Programmsyntheseverfahren, das ausgehend von Existenzaussagen, die als formale Programmspezifikationen aufgefa~t werden, rekursive Programme erzeugt. Kann ein solches Programm korrekt erstellt werden, so beschreibt der Syntheseproze~ gleichzeitig einen Induktionsbeweis der entsprechenden Existenzaussage. Auf der Basis dieses Verfahrens wurde ein automatisches Programmsynthesesystem entwickelt und implementiert. Es verwendet spezielle Transformationsregeln sowie Strategien und Heuristiken, die die Beweissuche steuern. Sie werden anhand vieler Beispiele ausf}hrlich diskutiert. Obwohl die hier beschriebene Methode in erster Linie zur Automatisierung von Existenzbeweisen entwickelt worden ist, und der Aspekt der automatischen Softwareentwicklung eher im Hintergrund steht, motivieren zahlreiche Beispiele dazu, das Verfahren auch f}r diesen Zweck einzusetzen.
目次
1. Einfuhrung.- 2. UEbersicht.- 3. Formale Grundbegriffe.- 3.1 Syntaktische Grundbegriffe.- 3.2 Semantische Grundbegriffe.- 3.3 Theoriespezifikationen.- 4. Beweis durch Synthese.- 4.1 Der Synthesekalkul.- 4.2 Korrektheit.- 5. Transformationsregeln.- 5.1 Induktionsregeln.- 5.2 Normalisierung.- 5.3 Termersetzungsregeln.- 5.4 Fallunterscheidungsregeln.- 5.5 Extraktionsregeln.- 5.6 Implikationenregel.- 5.7 Eliminationsregel.- 6. Das Syntheseverfahren als Existenzbeweismethode.- 6.1 Auswahl eines geeigneten Induktionsaxioms.- 6.2 Konstruktion eines loesenden Terms.- 6.3 Verwendung von Eigenschaften des loesenden Terms zum Beweis.- 7. Die Mechanisierung des Verfahrens.- 7.1 Die Struktur des Suchraumes.- 7.2 Die Suchstrategie.- 7.3 Die vier Phasen des Syntheseprozesses.- 7.4 Die Zulassigkeit des synthetisierten Programmes.- 8. Heuristiken.- 8.1 Auswahl der Induktionsaxiome.- 8.2 Symbolische Auswertung.- 8.3 Verwendung von Induktionshypothesen.- 8.4 Loesung von Konflikten.- 8.5 Verwendung von Bedingungen.- 8.6 Auswahl von Restformeln.- 8.7 Bewertung von Regelanwendungen.- 9. Beispiele.- 9.1 Die Vollstandigkeit eines Beweisers fur Aussagenlogik.- 9.2 Die Synthese einer Funktion zur Umkehrung von Listen.- 9.3 Die Synthese einer Sortierfunktion.- 9.4 Die Synthese von ganzzahligem Quotient und Rest.- 10. Schlussbemerkungen.- Literatur.- Anhang A: Sorten, Stellen und Ordnungsrelationen.- Anhang B: Verzeichnis der Symbole und Abkurzungen.
「Nielsen BookData」 より
