Chris Hardin and Dexter Kozen. On the Complexity of the Horn Theory of REL. Technical Report TR2003-1896, Computer Science Department, Cornell University, May 2003.

We show that the universal Horn theory of relational Kleene algebras is Pi-1-1-complete.