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

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Logic-Based Program Synthesis and Transformation : 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers
Redaktører	Fabio Fioravanti, John P. Gallagher
Antal sider	15
Forlag	Springer
Publikationsdato	10 jul. 2018
Sider	164-179
ISBN (Trykt)	978-3-319-94459-3
ISBN (Elektronisk)	978-3-319-94460-9
DOI	https://doi.org/10.1007/978-3-319-94460-9_10
Status	Udgivet - 10 jul. 2018
Begivenhed	LOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation - University of Namur, Namur, Belgien Varighed: 10 okt. 2017 → 12 okt. 2017 Konferencens nummer: 27 https://www.sci.unich.it/lopstr17/

Symposium

Symposium	LOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation
Nummer	27
Lokation	University of Namur
Land	Belgien
By	Namur
Periode	10/10/2017 → 12/10/2017
Internetadresse	https://www.sci.unich.it/lopstr17/

Navn	Lecture Notes in Computer Science
Vol/bind	10855
ISSN	0302-9743

Navn	Theoretical Computer Science and General Issues
Vol/bind	10855

Link til dokument

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

Kirkeby2017Indsendt manuskript, 379 KBLicens: Andet

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

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. red. / Fabio Fioravanti ; John P. Gallagher. Springer, 2018. s. 164-179 (Lecture Notes in Computer Science, Bind 10855). (Theoretical Computer Science and General Issues, Bind 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. i F Fioravanti & JP Gallagher (red), 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, bind 10855, Theoretical Computer Science and General Issues, bind 10855, s. 164-179, LOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation , Namur, Belgien, 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. red. / Fabio Fioravanti; John P. Gallagher. Springer, 2018. s. 164-179 (Lecture Notes in Computer Science, Bind 10855). (Theoretical Computer Science and General Issues, Bind 10855).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › 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. I Fioravanti F, Gallagher JP, red., Logic-Based Program Synthesis and Transformation: 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers. Springer. 2018. s. 164-179. (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