A Distribution Semantics for Probabilistic Term Rewriting
This work addresses the need for probabilistic modeling in computational formalisms like term rewriting, which is incremental as it builds on existing rewriting systems by adding probability.
The authors tackled the problem of modeling uncertainty in term rewriting systems by defining a novel distribution semantics that calculates the probability of reducing a term to a value, and they developed an efficient method to compute explanations for reductions.
Probabilistic programming is becoming increasingly popular thanks to its ability to specify problems with a certain degree of uncertainty. In this work, we focus on term rewriting, a well-known computational formalism. In particular, we consider systems that combine traditional rewriting rules with probabilities. Then, we define a novel "distribution semantics" for such systems that can be used to model the probability of reducing a term to some value. We also show how to compute a set of "explanations" for a given reduction, which can be used to compute its probability in a more efficient way. Finally, we illustrate our approach with several examples and outline a couple of extensions that may prove useful to improve the expressive power of probabilistic rewrite systems.