Hostname: page-component-7b7567c8c-slfcl Total loading time: 0 Render date: 2026-11-19T19:53:49.741Z Has data issue: false hasContentIssue false

CoLoR: a Coq library on well-founded rewrite relations and its application to the automated verification of termination certificates

Published online by Cambridge University Press:  01 July 2011

FRÉDÉRIC BLANQUI
Affiliation:
INRIA, FIT 3-604, Tsinghua University, Haidian District, Beijing 100084, China Email: frederic.blanqui@inria.fr
ADAM KOPROWSKI
Affiliation:
MLstate, 15 Rue Berlier, 75013 Paris, France Email: adam.koprowski@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 at http://color.inria.fr/.