Dexter Kozen. On the representation of Kleene algebras with tests. In R. Královic and P. Urzyczyn, editors, Proc. Conf. Mathematical Foundations of Computer Science (MFCS'06), volume 4162 of Lecture Notes in Computer Science, pages 73-83. Springer, August 2006.

We investigate conditions under which a given Kleene algebra with tests is isomorphic to an algebra of binary relations. Two simple separation properties are identified that, along with star-continuity, are sufficient for nonstandard relational representation. An algebraic condition is identified that is necessary and sufficient for the construction to produce a standard representation.