Automatische Synthese rekursiver Programme als Beweisverfahren (Informatik-Fachberichte, 302) (German Edition)

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. Front Matter....Pages N2-VIII Einführung....Pages 1-13 Übersicht....Pages 15-17 Formale Grundbegriffe....Pages 19-41 Beweis durch Synthese....Pages 43-56 Transformationsregeln....Pages 57-90 Das Syntheseverfahren als Existenzbeweismethode....Pages 91-111 Die Mechanisierung des Verfahrens....Pages 113-145 Heuristiken....Pages 147-192 Beispiele....Pages 193-240 Schlußbemerkungen....Pages 241-243 Back Matter....Pages 245-259