On the Complexity of the Horn Theory of REL

File(s)

Permanent Link(s)

Collections

Author

Hardin, Chris

Kozen, Dexter

Abstract

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

Date Issued

2003-05-08

Publisher

Cornell University

Keywords

•

Previously Published as

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2003-1896

Type

technical report