paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Completeness Theorem for Probabilistic Regular Expressions

概率正则表达式的完备性定理
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 该论文研究概率正则表达式的完备性定理，属于形式语言与自动机理论，与用户关注的静态分析、Agentic程序、浮点/贝叶斯程序分析及LLM交叉均无直接关联。虽然涉及概率和Kleene代数，但更偏纯理论，缺乏工程实现与LLM结合，因此匹配度低。引用 4 inbox
Wojciech Różowski, Alexandra Silva
形式语义逻辑与自动机
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话：引入概率正则表达式，并证明其基于Kleene代数公理化的概率语言等价推理系统具有完备性。

论文引入概率正则表达式（PRE），作为经典正则表达式在概率语言上的对应物：每个单词被赋予一个被生成的概率。作者定义 PRE 的概率语言语义，并研究其语言等价问题。基于 Salomaa 对 Kleene 代数的公理化，论文给出一个用于推导 PRE 概率语言等价的推理系统，并证明该系统相对该语义是完备的。该结果把经典正则表达式的代数完备性推广到概率情形，为概率语言等价提供公理化推理基础。

问题
如何在概率语言上建立正则表达式的公理化推理，并刻画其概率语言等价。
方法
引入概率正则表达式（PRE）与概率语言语义，基于 Salomaa 的 Kleene 代数公理化构造用于概率语言等价的推理系统。
评估
通过理论证明展示该推理系统对 PRE 的概率语言等价是完备的。
原文摘要（Abstract）

We introduce Probabilistic Regular Expressions (PRE), a probabilistic analogue of regular expressions denoting probabilistic languages in which every word is assigned a probability of being generated. We present and prove the completeness of an inference system for reasoning about probabilistic language equivalence of PRE based on Salomaa's axiomatisation of Kleene Algebra.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@inproceedings{abs-2310-08779,
  title = {A Completeness Theorem for Probabilistic Regular Expressions},
  author = {Wojciech Różowski and Alexandra Silva},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662084}
}