Research work · 1997

Kleene algebra with tests

Dexter C. Kozen

ACM Transactions on Programming Languages and Systems

Abstract

We introduce Kleene algebra with tests, an equational system for manipulating programs. We give a purely equational proof, using Kleene algebra with tests and commutativity conditions, of the following classical result: every while program can be simulated by a while program can be simulated by a while program with at most one while loop. The proof illustrates the use of Kleene algebra with tests and commutativity conditions in program equivalence proofs.

Download PDF

DOI: 10.1145/256167.256195