Probabilistic Rewriting: On Normalization, Termination, and Unique Normal Forms
Claudia Faggian · arXiv (Cornell University) · 2018
While a mature body of work supports the study of rewriting systems, even infinitary ones, abstract tools for Probabilistic Rewriting are still limited. Here, we investigate questions such as uniqueness of the result (unique limit distribution) and we develop a set of proof techniques to analyze and compare reduction strategies. The goal is to have tools to support the operational analysis of probabilistic calculi (such as probabilistic lambda-calculi) whose evaluation is also non-deterministic, in the sense that different reductions are possible. In particular, we investigate how the behavior of different rewrite sequences starting from the same term compare w.r.t. normal forms, and propose a robust analogue of the notion of unique normal form. Our approach is that of Abstract Rewrite Systems, i.e. we search for general properties of probabilistic rewriting, which hold independently of the specific structure of the objects.