Mechanically certifying formula-based Noetherian induction reasoning. (May 2017)

• Record Type: Journal Article
• Authors: Stratulat, Sorin
• Is Part Of: Journal of symbolic computation. Volume 80:Part 1(2017)
• Page Start: 209
• Page End: 249
• Publication Date: 2017-05
• Subjects: Noetherian induction -- Cyclic induction proofs -- Implicit induction proofs -- Proof certification -- Coq -- SPIKE; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.07.014
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In first-order logic, the formula-based instances of the Noetherian induction principle allow to perform effectively simultaneous, mutual and lazy induction reasoning. Compared to the term-based Noetherian induction instances, they are not directly supported by the current proof assistants. We provide general formal tools for certifying formula-based Noetherian induction proofs by the Coq proof assistant, then show how to apply them to certify proofs of conjectures about conditional specifications, built with: i) a reductive rewrite-based induction system, and ii) a reductive-free cyclic induction system. The generation of reductive proofs and their certification process can be easily automatised, without requiring additional definitions or proof transformations, but may involve many ordering constraints to be checked during the certification process. On the other hand, the reductive-free proofs generate fewer ordering constraints, may involve more general specifications and the certification process is more effective. However, their proof generation is less automatic and the generated proofs need to be normalised before being certified. The methodology for certifying reductive-free cyclic induction proofs related to conditional specifications extends a previous approach used for implicit induction proofs and it can be easily adapted to certify any formula-based Noetherian induction reasoning. In practice, the methodology has been implemented to automatically certify implicit induction proofs generated by the SPIKE theorem prover as well as reductive-free cyclic proofs built by the same system but in a less automatic way.