A Completeness Theorem for Probabilistic Regular Expressions
arXiv:2310.08779
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.
Accepted for publication at LICS. Full version of the paper containing omitted proofs