Confluence and convergence modulo equivalence in probabilistically terminating reduction systems

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review


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.
TidsskriftInternational Journal of Approximate Reasoning
Sider (fra-til)217-228
Antal sider12
StatusUdgivet - feb. 2019


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

Citer dette