Induction for Positive Almost Sure Termination - Extended version - - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Induction for Positive Almost Sure Termination - Extended version -

Résumé

In this paper, we propose an inductive approach to prove positive almost sure termination of probabilistic rewriting under the innermost strategy. We extend to the probabilistic case a technique we proposed for termination of usual rewriting under strategies. The induction principle consists in assuming that terms smaller than the starting terms for an induction ordering are positively almost surely terminating. The proof is developed in generating proof trees, modelizing rewriting trees, in alternatively applying abstraction steps, expressing the application of the induction hypothesis, and narrowing steps, simulating the possible rewriting steps after abstraction. This technique is fully automatable for rewrite systems on constants, very useful to modelize probabilistic protocols.
Fichier principal
Vignette du fichier
IPAS-termin-extended.pdf (281.4 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00147450 , version 1 (17-05-2007)
inria-00147450 , version 2 (20-05-2007)

Identifiants

  • HAL Id : inria-00147450 , version 2

Citer

Isabelle Gnaedig. Induction for Positive Almost Sure Termination - Extended version -. [Research Report] 2007, pp.16. ⟨inria-00147450v2⟩
107 Consultations
69 Téléchargements

Partager

Gmail Facebook X LinkedIn More