LATPub629: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
(kein Unterschied)
|
Aktuelle Version vom 25. März 2015, 16:34 Uhr
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},
}