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