A Completeness Theorem for Probabilistic Regular Expressions

2023/10/12 by Różowski, Wojciech, Silva, Alexandra
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/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.

Related

• P(Expression|Grammar): Probability of deriving an algebraic expression with a probabilistic context-free grammar
• Probabilistic Automata for Computing with Words
• Relatively Complete Verification of Probabilistic Programs
• A Complete Axiomatisation of Equivalence for Discrete Probabilistic Programming
• Probability Distributions Over Possible Worlds