On the Complexity of the Horn Theory of REL

Abstract

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

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 08, 2003
Accession Number
AD1000501

Entities

People

  • Chris Hardin
  • Dexter Kozen

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Alphabets
  • Automata
  • Automata Theory
  • Computations
  • Computer Science
  • Construction
  • Equations
  • Finite Alphabet
  • Formal Languages
  • Language
  • Machines
  • New York
  • Relational Database Management Systems
  • Scanning
  • Standards
  • Symbols
  • Transitions

Fields of Study

  • Mathematics