Confluence and Convergence in Probabilistically Terminating Reduction Systems

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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.
LanguageEnglish
Title of host publicationLogic-Based Program Synthesis and Transformation : 27th International Symposium, LOPSTR 2017, Namur, Belgium, October 10-12, 2017, Revised Selected Papers
EditorsFabio Fioravanti, John P. Gallagher
Number of pages15
PublisherSpringer
Date10 Jul 2018
Pages164-179
ISBN (Print)978-3-319-94459-3
ISBN (Electronic)978-3-319-94460-9
DOIs
Publication statusPublished - 10 Jul 2018
EventLOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation - University of Namur, Namur, Belgium
Duration: 10 Oct 201712 Oct 2017
Conference number: 27

Symposium

SymposiumLOPSTR 2017 - International Symposium on Logic-Based Program Synthesis and Transformation
Number27
LocationUniversity of Namur
CountryBelgium
CityNamur
Period10/10/201712/10/2017
SeriesLecture Notes in Computer Science
Volume10855
ISSN0302-9743
SeriesTheoretical Computer Science and General Issues
Volume10855

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 = "7",
day = "10",
doi = "10.1007/978-3-319-94460-9_10",
language = "English",
isbn = "978-3-319-94459-3",
pages = "164--179",
editor = "Fabio Fioravanti and Gallagher, {John P.}",
booktitle = "Logic-Based Program Synthesis and Transformation",
publisher = "Springer",

}

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.

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Confluence and Convergence in Probabilistically Terminating Reduction Systems

AU - Kirkeby, Maja Hanne

AU - Christiansen, Henning

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

SP - 164

EP - 179

BT - Logic-Based Program Synthesis and Transformation

A2 - Fioravanti, Fabio

A2 - Gallagher, John P.

PB - Springer

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