HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Proving Positive Almost-Sure Termination

Olivier Bournez 1 Florent Garnier 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Contributor : Olivier Bournez Connect in order to contact the contributor
Submitted on : Wednesday, October 26, 2005 - 7:15:07 PM
Last modification on : Friday, May 13, 2022 - 10:18:05 PM




Olivier Bournez, Florent Garnier. Proving Positive Almost-Sure Termination. 16th International Conference on Rewriting Techniques and Applications - RTA'2005, Apr 2005, Nara/Japan, pp.323-337, ⟨10.1007/b135673⟩. ⟨inria-00000522⟩



Record views