Back to Search
Start Over
A Completeness Theorem for Probabilistic Regular Expressions
- Publication Year :
- 2023
-
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.<br />Comment: Accepted for publication at LICS. Full version of the paper containing omitted proofs
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2310.08779
- Document Type :
- Working Paper