Accession Number:

AD1000501

Title:

On the Complexity of the Horn Theory of REL

Descriptive Note:

Technical Report

Corporate Author:

CORNELL UNIV ITHACA NY ITHACA

Personal Author(s):

Report Date:

2003-05-08

Pagination or Media Count:

13.0

Abstract:

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

Descriptors:

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE