A NEXPTIME-complete Description Logic Strictly Contained in C^2
Aus International Center for Computational Logic
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
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},
}
