A Completeness Theorem for Probabilistic Regular Expressions

Wojciech Rozowski; Alexandra Silva

doi:10.1145/3661814.3662084

LICS2024顶会

A Completeness Theorem for Probabilistic Regular Expressions

Wojciech Rozowski, Alexandra Silva

arXiv DOI 出版方

2024年份

3被引次数

摘要

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.