[isabelle] New AFP Entry: Regular Algebras

Regular Algebras
Simon Foster and Georg Struth

Regular algebras axiomatise the equational theory of regular expressions as
induced by regular language identity. We use Isabelle/HOL for a detailed
systematic study of regular algebras given by Boffa, Conway, Kozen and Salomaa.
We investigate the relationships between these classes, formalise a soundness
proof for the smallest class (Salomaa's) and obtain completeness of the largest
one (Boffa's) relative to a deep result by Krob. In addition we provide a large
collection of regular identities in the general setting of Boffa's axiom. Our
regular algebra hierarchy is orthogonal to the Kleene algebra hierarchy in the
Archive of Formal Proofs; we have not aimed at an integration for pragmatic reasons.



This archive was generated by a fusion of Pipermail (Mailman edition) and MHonArc.