Tags:Automata, Axiomatisation, Cyclic proofs, Induction, Kleene algebra and Regular languages

Abstract:

We give a new proof that the axioms of left-handed Kleene algebra are complete with respect to language containments. This proof is significantly simpler than both the proof of Boffa (which relies on Krob's completeness result), and the more recent proof of Kozen and Silva. Our proof builds on a recent non-wellfounded sequent calculus which makes it possible to explicitly compute the invariants required for left-handed Kleene algebra.

Completeness of Left Handed Kleene algebra via Cyclic Proofs