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

From International Center for Computational Logic
Toggle side column

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

Stephan TobiesStephan Tobies
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
  • 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},
}