Proving Positive Almost-Sure Termination - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2004

Proving Positive Almost-Sure Termination

Résumé

In order to extend the modeling capabilities of rewriting systems, it is rather natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules subject to probabilities leads to numerous questions about the underlying notions and results. We focus here on the problem of termination of a set of probabilistic rewrite rules. A probabilistic rewrite system is said almost surely terminating if the probability that a derivation leads to a normal form is one. Such a system is said positively almost surely terminating if furthermore the mean length of a derivation is finite. We provide several results and techniques in order to prove positive almost sure termination of a given set of probabilistic rewrite rules. All these techniques subsume classical ones for non-probabilistic systems.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
A04-R-409.pdf (216.91 Ko) Télécharger le fichier

Dates et versions

inria-00099867 , version 1 (26-09-2006)

Identifiants

  • HAL Id : inria-00099867 , version 1

Citer

Olivier Bournez, Florent Garnier. Proving Positive Almost-Sure Termination. [Intern report] A04-R-409 || bournez04h, 2004, 16 p. ⟨inria-00099867⟩
83 Consultations
374 Téléchargements

Partager

Gmail Facebook X LinkedIn More