Confluence and Convergence in Probabilistically Terminating Reduction Systems

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

Convergence of an abstract reduction system (ARS) is the property that any derivation from an initial state will end in the same final state, a.k.a. normal form. We generalize this for probabilistic ARS as almost-sure convergence, meaning that the normal form is reached with probability one, even if diverging derivations may exist. We show and exemplify properties that can be used for proving almost-sure convergence of probabilistic ARS, generalizing known results from ARS.
OriginalsprogEngelsk
TitelLogic-Based Program Synthesis and Transformation : 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers
RedaktørerFabio Fioravanti, John P. Gallagher
Antal sider15
ForlagSpringer
Publikationsdato10 jul. 2018
Sider164-179
ISBN (Trykt)978-3-319-94459-3
ISBN (Elektronisk)978-3-319-94460-9
DOI
StatusUdgivet - 10 jul. 2018
BegivenhedLOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation - University of Namur, Namur, Belgien
Varighed: 10 okt. 201712 okt. 2017
Konferencens nummer: 27
https://www.sci.unich.it/lopstr17/

Symposium

SymposiumLOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation
Nummer27
LokationUniversity of Namur
LandBelgien
ByNamur
Periode10/10/201712/10/2017
Internetadresse
NavnLecture Notes in Computer Science
Vol/bind10855
ISSN0302-9743
NavnTheoretical Computer Science and General Issues
Vol/bind10855

Citer dette

Kirkeby, M. H., & Christiansen, H. (2018). Confluence and Convergence in Probabilistically Terminating Reduction Systems. I F. Fioravanti, & J. P. Gallagher (red.), Logic-Based Program Synthesis and Transformation: 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers (s. 164-179). Springer. Lecture Notes in Computer Science, Bind. 10855, Theoretical Computer Science and General Issues, Bind. 10855 https://doi.org/10.1007/978-3-319-94460-9_10