Published on Mon Apr 16 2018

Probabilistic Rewriting and Asymptotic Behaviour: on Termination and Unique Normal Forms

See More ...

While a mature body of work supports the study of rewriting systems, abstract tools for Probabilistic Rewriting are still limited. In this paper we study the question of uniqueness of the result (unique limit distribution), and develop a set of proof techniquesto analyze and compare reduction strategies. The goal is to have tools to support the operational analysis of probabilistic calculi (such as probabilistic lambda-calculi) where evaluation is not justa single strategy, but different reduction choices are allowed (hence different reduction paths).