# A Distribution Semantics for Probabilistic Term Rewriting

arXiv: https://arxiv.org/abs/2410.15081 · HTML: https://mlsanity.com/paper/2410.15081/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 47 references that are in the map.
- First posted on arXiv 19 Oct 2024.

## Builds on (most cited first, 7 of 7)

- [On the Semantics and Complexity of Probabilistic Logic Programs](https://mlsanity.com/paper/1701.09000/) (2017)
- [Confluence in Probabilistic Rewriting](https://mlsanity.com/paper/1708.03536/) (2017)
- [Confluence and Convergence in Probabilistically Terminating Reduction Systems](https://mlsanity.com/paper/1709.05123/) (2017)
- [Probabilistic Rewriting and Asymptotic Behaviour: on Termination and Unique Normal Forms](https://mlsanity.com/paper/1804.05578/) (2018)
- [A Complete Dependency Pair Framework for Almost-Sure Innermost Termination of Probabilistic Term Rewriting](https://mlsanity.com/paper/2309.00344/) (2023)
- [From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting](https://mlsanity.com/paper/2310.06121/) (2023)
- [Explaining Explanations in Probabilistic Logic Programming](https://mlsanity.com/paper/2401.17045/) (2024)

## Abstract (arXiv)

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.