Browse DORAS
Browse Theses
Search
Latest Additions
Creative Commons License
Except where otherwise noted, content on this site is licensed for use under a:

Automatic inductive theorem proving and program construction methods using program transformation

Kabir, Md. Humayun (2007) Automatic inductive theorem proving and program construction methods using program transformation. PhD thesis, Dublin City University.

Full text available as:

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
13Mb

Abstract

We present new approaches to prove universally and existentially quantified conjectures and to construct programs from the resulting proofs. These theorem proving and program construction techniques make use of the distillation algorithm to transform input conjectures into a normalised form which we call distilled form. The proof rules are applied to the resulting distilled program. Our theorem proving and program construction techniques have been implemented in a theorem prover which we call Poitin. We give an overview of the distillation algorithm, and then present the proof and program construction techniques implemented in Poitin. Our implementation of the proof and program construction techniques used in Poitin is then presented. The soundness of the proof technique is shown with respect to a logical proof system using sequent calculus. We show that the constructed programs are correct with respect to their specification. The main contributions of this thesis can be summarised as follows. First, we present fully automatic, and efficient inductive theorem proving techniques. Second, we present a novel program construction technique to construct correct programs. Third, we have shown how automatic program transformation can be used in a novel way in an inductive theorem prover. Finally, the use of distillation to obtain a normal form of the input program reduces over-generalization and generation of non-theorems. We have implemented the theorem prover and demonstrated it on some examples. The use of distillation in the framework of Poitin has eased the automation of the proof and program construction techniques in a reduced search space to make it fully automatic and efficient.

Item Type:Thesis (PhD)
Date of Award:2007
Refereed:No
Supervisor(s):Hamilton, Geoff
Uncontrolled Keywords:theorem proving techniques; program construction techniques; automatic program transformation; inductive theorems; proof automation
Subjects:UNSPECIFIED
DCU Faculties and Centres:DCU Faculties and Schools > Faculty of Engineering and Computing > School of Computing
Use License:This item is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 3.0 License. View License
ID Code:16990
Deposited On:14 May 2012 11:19 by Fran Callaghan. Last Modified 14 May 2012 11:19

Download statistics

Archive Staff Only: edit this record