A {NExpTime}-complete Description Logic Strictly Contained in {$C^2$}

S~.TobiesS~.Tobies

Datei:Tobies-CSL-1999.ps.gz

Download

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

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.

There is also an extended technical report.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@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},
}