Proving Positive Almost-Sure Termination
Identifieur interne : 004272 ( Crin/Curation ); précédent : 004271; suivant : 004273Proving Positive Almost-Sure Termination
Auteurs : Olivier Bournez ; Florent GarnierSource :
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.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :004272
Links to Exploration step
CRIN:bournez05aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="269">Proving Positive Almost-Sure Termination</title></titleStmt><publicationStmt><idno type="RBID">CRIN:bournez05a</idno><date when="2005" year="2005">2005</date><idno type="wicri:Area/Crin/Corpus">004272</idno><idno type="wicri:Area/Crin/Curation">004272</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">004272</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Proving Positive Almost-Sure Termination</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></author><author><name sortKey="Garnier, Florent" sort="Garnier, Florent" uniqKey="Garnier F" first="Florent" last="Garnier">Florent Garnier</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="1501">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.</div></front></TEI><BibTex type="inproceedings"><ref>bournez05a</ref><crinnumber>A05-R-261</crinnumber><category>3</category><equipe>PROTHEO</equipe><author><e>Bournez, Olivier</e><e>Garnier, Florent</e></author><title>Proving Positive Almost-Sure Termination</title><booktitle>{16th International Conference on Rewriting Techniques and Applications - RTA'2005, Nara, Japan}</booktitle><year>2005</year><editor>Jürgen Giesl</editor><volume>3467</volume><series>Lecture Notes in Computer Science</series><pages>323--337</pages><month>Apr</month><publisher>Springer Verlag</publisher><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.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004272 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Curation/biblio.hfd -nk 004272 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Curation
|type= RBID
|clé= CRIN:bournez05a
|texte= Proving Positive Almost-Sure Termination
}}
| This area was generated with Dilib version V0.6.33. |  |