A NEXPTIME-complete Description Logic Strictly Contained in C^2

Stephan TobiesStephan Tobies

Datei:Tobies-LTCS-99-05.ps.gz

Download

Stephan Tobies
A NEXPTIME-complete Description Logic Strictly Contained in C^2
Technical Report, LuFG Theoretical Computer Science, RWTH Aachen, volume LTCS-99-05, 1999. LTCS-Report

Details
Bibtex

KurzfassungAbstract
We examine the complexity and expressivity of the combination of the Description Logic ALCQI with a terminological formalism based on cardinality restrictions on concepts. This combination can naturally be embedded into C^2, the two variable fragment of predicate logic with counting quantifiers. We prove that ALCQI has the same complexity as C^2 but does not reach its expressive power.
Bemerkung: Note: An abriged version appeared at CSL-99.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Tobies-LTCS-99-05,
  address = {Germany},
  author = {S. {Tobies}},
  institution = {LuFG Theoretical Computer Science, RWTH Aachen},
  note = {An abriged version appeared at CSL-99.},
  number = {LTCS-99-05},
  title = {A NEXPTIME-complete Description Logic Strictly Contained in {$C^2$}},
  type = {LTCS-Report},
  year = {1999},
}