Weak Kleene Algebra is Sound and (Possibly) Complete for Simulation

2009/10/06 by Cohen, Ernie
#F.1.2 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Programming Languages (cs.PL)

paper · doi:10.48550/arxiv.0910.1028

Abstract

We show that the axioms of Weak Kleene Algebra (WKA) are sound and complete for the theory of regular expressions modulo simulation equivalence, assuming their completeness for monodic trees (as conjectured by Takai and Furusawa).

Related

• Kleene Algebra
• An Elementary Proof of the FMP for Kleene Algebra
• Weak Concurrent Kleene Algebra with Application to Algebraic Verification
• A Coalgebraic Approach to Kleene Algebra with Tests
• Kleene Algebra with Dynamic Tests: Completeness and Complexity