A NExpTime-complete Description Logic Strictly Contained in C^2
From International Center for Computational Logic
A NExpTime-complete Description Logic Strictly Contained in C^2
S .TobiesS .Tobies
S .Tobies
A NExpTime-complete Description Logic Strictly Contained in C^2
In J. Flum and M. Rodríguez-Artalejo, eds., Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL-99), LNCS 1683, 292-306, 1999. Springer
A NExpTime-complete Description Logic Strictly Contained in C^2
In J. Flum and M. Rodríguez-Artalejo, eds., Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL-99), LNCS 1683, 292-306, 1999. Springer
- 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.
There is also an extended technical report.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Tobies-CSL-99,
author = {{S~.Tobies}},
booktitle = {Proceedings of the Annual Conference of the European Association for Computer Science Logic {(CSL-99)}},
editor = {J. {Flum} and M. {Rodr{\'i}guez-Artalejo}},
pages = {292--306},
publisher = {Springer-Verlag},
series = {LNCS 1683},
title = {A {NExpTime}-complete Description Logic Strictly Contained in {$C^2$}},
year = {1999},
}
