  We present a Coq library about Kleene algebra with tests, including a proof
of their completeness over the appropriate notion of languages, a decision
procedure for their equational theory, and tools for exploiting hypotheses of a
particular shape in such a theory. Kleene algebra with tests make it possible
to represent if-then-else statements and while loops in most imperative
programming languages. They were actually introduced by Kozen as an alternative
to propositional Hoare logic. We show how to exploit the corresponding Coq
tools in the context of program verification by proving equivalences of while
programs, correctness of some standard compiler optimisations, Hoare rules for
partial correctness, and a particularly challenging equivalence of flowchart
schemes.
