Confluence and convergence modulo equivalence in probabilistically terminating reduction systems

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

Convergence of an abstract reduction system is the property that the possible derivations from a given initial state all end in the same final state. Relaxing this by “modulo equivalence” means that these final states need not be identical, only equivalent wrt. a specified equivalence relation.

We generalize this notion for probabilistic abstract reduction systems, naming it almost-sure convergence modulo equivalence, such that the final states are reached with probability 1. We relate it to the well-studied properties of almost-sure termination and confluence/convergence of probabilistic and non-probabilistic systems. In addition, we provide a transformational approach for proving – or disproving – almost-sure convergence modulo equivalence of given systems.
Original languageEnglish
JournalInternational Journal of Approximate Reasoning
Volume105
Pages (from-to)217-228
ISSN0888-613X
DOIs
Publication statusPublished - 2019

Keywords

  • Almost-sure convergence modulo equivalence
  • Almost-sure termination
  • Probabilistic abstract reduction systems
  • Abstract reduction systems
  • Confluence modulo equivalence

Cite this

@article{29664f90c84d44cbab15044e1a6edf78,
title = "Confluence and convergence modulo equivalence in probabilistically terminating reduction systems",
abstract = "Convergence of an abstract reduction system is the property that the possible derivations from a given initial state all end in the same final state. Relaxing this by “modulo equivalence” means that these final states need not be identical, only equivalent wrt. a specified equivalence relation.We generalize this notion for probabilistic abstract reduction systems, naming it almost-sure convergence modulo equivalence, such that the final states are reached with probability 1. We relate it to the well-studied properties of almost-sure termination and confluence/convergence of probabilistic and non-probabilistic systems. In addition, we provide a transformational approach for proving – or disproving – almost-sure convergence modulo equivalence of given systems.",
keywords = "Almost-sure convergence modulo equivalence, Almost-sure termination, Probabilistic abstract reduction systems, Abstract reduction systems, Confluence modulo equivalence, Almost-sure convergence modulo equivalence, Almost-sure termination, Probabilistic abstract reduction systems, Abstract reduction systems, Confluence modulo equivalence",
author = "Kirkeby, {Maja Hanne} and Henning Christiansen",
year = "2019",
doi = "10.1016/j.ijar.2018.11.018",
language = "English",
volume = "105",
pages = "217--228",
journal = "International Journal of Approximate Reasoning",
issn = "0888-613X",
publisher = "Elsevier Inc.",

}

Confluence and convergence modulo equivalence in probabilistically terminating reduction systems. / Kirkeby, Maja Hanne; Christiansen, Henning.

In: International Journal of Approximate Reasoning, Vol. 105, 2019, p. 217-228.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Confluence and convergence modulo equivalence in probabilistically terminating reduction systems

AU - Kirkeby, Maja Hanne

AU - Christiansen, Henning

PY - 2019

Y1 - 2019

N2 - Convergence of an abstract reduction system is the property that the possible derivations from a given initial state all end in the same final state. Relaxing this by “modulo equivalence” means that these final states need not be identical, only equivalent wrt. a specified equivalence relation.We generalize this notion for probabilistic abstract reduction systems, naming it almost-sure convergence modulo equivalence, such that the final states are reached with probability 1. We relate it to the well-studied properties of almost-sure termination and confluence/convergence of probabilistic and non-probabilistic systems. In addition, we provide a transformational approach for proving – or disproving – almost-sure convergence modulo equivalence of given systems.

AB - Convergence of an abstract reduction system is the property that the possible derivations from a given initial state all end in the same final state. Relaxing this by “modulo equivalence” means that these final states need not be identical, only equivalent wrt. a specified equivalence relation.We generalize this notion for probabilistic abstract reduction systems, naming it almost-sure convergence modulo equivalence, such that the final states are reached with probability 1. We relate it to the well-studied properties of almost-sure termination and confluence/convergence of probabilistic and non-probabilistic systems. In addition, we provide a transformational approach for proving – or disproving – almost-sure convergence modulo equivalence of given systems.

KW - Almost-sure convergence modulo equivalence

KW - Almost-sure termination

KW - Probabilistic abstract reduction systems

KW - Abstract reduction systems

KW - Confluence modulo equivalence

KW - Almost-sure convergence modulo equivalence

KW - Almost-sure termination

KW - Probabilistic abstract reduction systems

KW - Abstract reduction systems

KW - Confluence modulo equivalence

U2 - 10.1016/j.ijar.2018.11.018

DO - 10.1016/j.ijar.2018.11.018

M3 - Journal article

VL - 105

SP - 217

EP - 228

JO - International Journal of Approximate Reasoning

JF - International Journal of Approximate Reasoning

SN - 0888-613X

ER -