Confluence and Convergence in Probabilistically Terminating Reduction Systems

Maja Hanne Kirkeby; Henning Christiansen

doi:10.1007/978-3-319-94460-9_10

Confluence and Convergence in Probabilistically Terminating Reduction Systems

Maja Hanne Kirkeby, Henning Christiansen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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.

Original language	English
Title of host publication	Logic-Based Program Synthesis and Transformation : 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers
Editors	Fabio Fioravanti, John P. Gallagher
Number of pages	15
Publisher	Springer
Publication date	10 Jul 2018
Pages	164-179
ISBN (Print)	978-3-319-94459-3
ISBN (Electronic)	978-3-319-94460-9
DOIs	https://doi.org/10.1007/978-3-319-94460-9_10
Publication status	Published - 10 Jul 2018
Event	LOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation - University of Namur, Namur, Belgium Duration: 10 Oct 2017 → 12 Oct 2017 Conference number: 27 https://www.sci.unich.it/lopstr17/

Symposium

Symposium	LOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation
Number	27
Location	University of Namur
Country	Belgium
City	Namur
Period	10/10/2017 → 12/10/2017
Internet address	https://www.sci.unich.it/lopstr17/

Series	Lecture Notes in Computer Science
Volume	10855
ISSN	0302-9743

Series	Theoretical Computer Science and General Issues
Volume	10855

Cite this

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

Kirkeby, Maja Hanne ; Christiansen, Henning. / Confluence and Convergence in Probabilistically Terminating Reduction Systems. Logic-Based Program Synthesis and Transformation: 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers. editor / Fabio Fioravanti ; John P. Gallagher. Springer, 2018. pp. 164-179 (Lecture Notes in Computer Science, Vol. 10855). (Theoretical Computer Science and General Issues, Vol. 10855).

@inproceedings{e41227cde2d34a608e6cc865732b8fb4,

title = "Confluence and Convergence in Probabilistically Terminating Reduction Systems",

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.",

author = "Kirkeby, {Maja Hanne} and Henning Christiansen",

year = "2018",

month = jul

day = "10",

doi = "10.1007/978-3-319-94460-9_10",

language = "English",

isbn = "978-3-319-94459-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "164--179",

editor = "Fabio Fioravanti and Gallagher, {John P.}",

booktitle = "Logic-Based Program Synthesis and Transformation",

note = "LOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation , LOPSTR 2017 ; Conference date: 10-10-2017 Through 12-10-2017",

url = "https://www.sci.unich.it/lopstr17/",

}

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

Confluence and Convergence in Probabilistically Terminating Reduction Systems. / Kirkeby, Maja Hanne ; Christiansen, Henning.

Logic-Based Program Synthesis and Transformation: 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers. ed. / Fabio Fioravanti; John P. Gallagher. Springer, 2018. p. 164-179 (Lecture Notes in Computer Science, Vol. 10855). (Theoretical Computer Science and General Issues, Vol. 10855).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Confluence and Convergence in Probabilistically Terminating Reduction Systems

AU - Kirkeby, Maja Hanne

AU - Christiansen, Henning

N1 - Conference code: 27

PY - 2018/7/10

Y1 - 2018/7/10

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-94460-9_10

DO - 10.1007/978-3-319-94460-9_10

M3 - Article in proceedings

SN - 978-3-319-94459-3

T3 - Lecture Notes in Computer Science

SP - 164

EP - 179

BT - Logic-Based Program Synthesis and Transformation

A2 - Fioravanti, Fabio

A2 - Gallagher, John P.

PB - Springer

T2 - LOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation

Y2 - 10 October 2017 through 12 October 2017

ER -

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

Link to document

10.1007/978-3-319-94460-9_10

Kirkeby2017Submitted manuscript, 379 KBLicence: Other