为带概率的项重写系统定义新语义，高效计算归约概率。
A Distribution Semantics for Probabilistic Term Rewriting
- 提出分布语义建模项归约到特定值的概率。
- 可生成归约解释集，加速概率计算。
- 适合研究概率编程与形式化推理的学者。
概率编程因其能描述不确定性问题而日益流行。本文聚焦于项重写这一经典计算形式化方法，特别关注结合传统重写规则与概率的系统。我们为此类系统定义了一种新的「分布语义」，用于建模将某个项归约到特定值的概率。同时，我们展示了如何为给定归约生成一组「解释」，从而更高效地计算其概率。最后，通过多个示例说明该方法，并展望若干可能提升概率重写系统表达能力的扩展方向。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。