s'authentifier
version française rss feed
!.. Document complet sous embargo ..!
Mise en ligne du document : document non public

inria-00107744, version 1

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

Olivier Fissore () a1, Isabelle Gnaedig () b1, Hélène Kirchner a1

N° A03-R-361 || fissore03c (2003)

Résumé : From an inductive method for proving weak innermost termination of rule-based programs, we automatically infer, for each successful proof, a finite strategy for data evaluation. The proof principle uses an explicit induction on the termination property, to prove that any input data has at least one finite evaluation. For that, we analyse proof trees built from the rewrite system, schematizing the innermost derivations of any ground term. These proof trees are issued from patterns representing sets of ground terms. They are generated using two mechanisms, namely abstraction, introducing variables that represent ground terms in normal form, and narrowing, schematizing rewriting on ground terms. From the proof trees, we can extract for any given ground term, a rewriting strategy to compute one of its normal form, even if the ground term admits infinite rewriting derivations.

  • a –  CNRS
  • b –  INRIA
  • 1 :  PROTHEO (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • Domaine : Informatique/Autre
  • Mots-clés : rewriting – weak termination – innermost – strategy – rule-based languages – induction – narrowing – ordering constraints || réécriture – terminaison faible – stratégie – langages a base de règles – surréduction – contraintes d'ordre
  • Référence interne : A03-R-361 || fissore03c
  • Commentaire : Rapport interne.
 
  • inria-00107744, version 1
  • oai:hal.inria.fr:inria-00107744
  • Contributeur : 
  • Soumis le : Jeudi 19 Octobre 2006, 09:07:38
  • Dernière modification le : Vendredi 20 Octobre 2006, 15:32:31
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...