On the Complexity of the Horn Theory of REL

Hardin, ChrisKozen, Dexter2007-04-042007-04-042003-05-08http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2003-1896https://hdl.handle.net/1813/5612We show that the universal Horn theory of relational Kleene algebras is Pi-1-1-complete.179155 bytesapplication/postscripten-UScomputer sciencetechnical reportOn the Complexity of the Horn Theory of RELtechnical report