CARIBOO: An Induction Based Proof Tool for Termination with Strategies

Olivier Fissore 1 Isabelle Gnaedig 1 Hélène Kirchner 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We describe Cariboo, the implementation of an inductive process recently proposed to prove termination of rewriting under strategies on ground term algebras. The method is based on an abstraction mechanism, introducing variables that represent ground terms in normal form, and on narrowing, schematizing reductions on ground terms. It applies in particular to non-terminating systems which are terminating with innermost or local strategies. The narrowing process, well known to easily diverge, is controlled by using appropriate abstraction constraints. The abstraction mechanism lies on satisfiability of ordering constraints. Thanks to the power of induction, these ordering constraints are often simple and automatically solved by our system. Otherwise, they can be treated by the user or any external automatic solver. On many examples, Cariboo even enables to succeed without considering any constraint at all; the process is then completely automatic. Cariboo offers a graphical view of the proof process. It is implemented in ELAN, a rule based programming environment, and so can be used for proving termination of ELAN programs.
Type de document :
Communication dans un congrès
Frank Pfennig. Fourth International Conference on Principles and Practice of Declarative Programming - PPDP'02, Oct 2002, Pittsburgh, USA, ACM Press, 12 p, 2002
Liste complète des métadonnées

https://hal.inria.fr/inria-00107557
Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 09:01:27
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57
Document(s) archivé(s) le : mercredi 29 mars 2017 - 13:07:02

Identifiants

  • HAL Id : inria-00107557, version 1

Collections

Citation

Olivier Fissore, Isabelle Gnaedig, Hélène Kirchner. CARIBOO: An Induction Based Proof Tool for Termination with Strategies. Frank Pfennig. Fourth International Conference on Principles and Practice of Declarative Programming - PPDP'02, Oct 2002, Pittsburgh, USA, ACM Press, 12 p, 2002. 〈inria-00107557〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

49