Proving weak termination also provides the right way to terminate - Extended version -

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 give an inductive method for proving weak innermost termination of rule-based programs, from which we automatically infer, for each successful proof, a finite strategy for data evaluation. We first present the proof principle, using an explicit induction on the termination property, to prove that any input data has at least one finite evaluation. For that, we observe proof trees built from the rewrite system, schematizing the innermost rewriting tree of any ground term, and generated with two mechanisms: abstraction, schematizing normalization of subterms, and narrowing, schematizing rewriting steps. Then, we show how, for any ground term, a normalizing rewriting strategy can be extracted from the proof trees, even if the ground term admits infinite rewriting derivations.
Type de document :
Rapport
[Intern report] A04-R-522 || fissore04b, 2004, 54 p
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00099872
Contributeur : Isabelle Gnaedig <>
Soumis le : vendredi 19 juin 2009 - 19:14:13
Dernière modification le : jeudi 11 janvier 2018 - 06:19:59
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:28:48

Fichiers

Identifiants

  • HAL Id : inria-00099872, version 1

Collections

Citation

Olivier Fissore, Isabelle Gnaedig, Hélène Kirchner. Proving weak termination also provides the right way to terminate - Extended version -. [Intern report] A04-R-522 || fissore04b, 2004, 54 p. 〈inria-00099872〉

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

70