CoLoR: a Coq library on well-founded rewrite relations and its application to the automated verification of termination certificates
- 1 July 2011
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 21 (4) , 827-859
Abstract
Termination is an important property of programs, and is notably required for programs formulated in proof assistants. It is a very active subject of research in the Turing-complete formalism of term rewriting. Over the years, many methods and tools have been developed to address the problem of deciding termination for specific problems (since it is undecidable in general). Ensuring the reliability of those tools is therefore an important issue.In this paper we present a library formalising important results of the theory of well-founded (rewrite) relations in the proof assistant Coq. We also present its application to the automated verification of termination certificates, as produced by termination tools.The sources are freely available athttp://color.inria.fr/.Keywords
All Related Versions
This publication has 49 references indexed in Scilit:
- Automated termination proofs for logic programs by term rewritingACM Transactions on Computational Logic, 2009
- Consistency and Completeness of Rewriting in the Calculus of ConstructionsLogical Methods in Computer Science, 2008
- Program-ing finger trees in C oqACM SIGPLAN Notices, 2007
- Modular development of certified program verifiers with a proof assistantACM SIGPLAN Notices, 2006
- Inductive definitions in the system Coq rules and properties2005
- Definitions by rewriting in the Calculus of ConstructionsMathematical Structures in Computer Science, 2005
- A compiled implementation of strong reductionACM SIGPLAN Notices, 2002
- Termination of term rewriting using dependency pairsTheoretical Computer Science, 2000
- Modularity of strong normalization in the algebraic-λ-cubeJournal of Functional Programming, 1997
- Orderings for term-rewriting systemsTheoretical Computer Science, 1982