Please use this identifier to cite or link to this item: doi:10.22028/D291-24941
Title: Using rippling to prove the termination of algorithms
Author(s): Hutter, Dieter
Language: English
Year of Publication: 1997
OPUS Source: Kaiserslautern ; Saarbrücken : DFKI, 1997
SWD key words: Künstliche Intelligenz
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: When proving theorems by explicit induction the used induction orderings are synthesized from the recursion orderings underlying the definition principles for functions and predicates. In order to guarantee the soundness of a generated induction scheme the well-foundedness of the used recursion orderings has to be proved. In this paper we present a method to synthesize appropriate measure functions in order to prove the termination of algorithms. We use Walthers' estimation-calculus as a "black-box procedure'; in these explicit proofs. Thus, we inherit both, the flexibility of an explicit representation of the termination proof as well as the in-built knowledge concerning the count ordering.
Link to this record: urn:nbn:de:bsz:291-scidok-38205
Series name: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Series volume: 97-03
Date of registration: 29-Jun-2011
Faculty: SE - Sonstige Einrichtungen
Department: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
RR_97_03.pdf269,68 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.