We present a reflexive tactic for deciding the equational theory of Kleene algebras in the Coq proof assistant. This tactic relies on a careful implementation of efficient finite automata algorithms, so that it solves casual equations almost instantaneously. The corresponding decision procedure was proved correct and complete; correctness is established w.r.t. any model (including binary relations), by formalising Kozen's initiality theorem.
Braibant and Pous REF implement a Coq tactic for deciding equational theory of Kleene algebras.
An Efficient Coq Tactic for Deciding Kleene Algebras
Lecture Notes in Computer Science
Lecture Notes in Computer Science
Computer Science