Mechanically certifying formula-based Noetherian induction reasoning
详细信息 查看全文
- 作者：Sorin Stratulat sorin.stratulat@univ-lorraine.fr
- 关键词：Noetherian induction ; Cyclic induction proofs ; Implicit induction proofs ; Proof certification ; Coq ; SPIKE
- 刊名：Journal of Symbolic Computation
- 出版年：2017
- 出版时间：May-June 2017
- 年：2017
- 卷：80
- 期：part_P1
- 页码：209-249
- 全文大小：784 K
- 卷排序：80
文摘
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.