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

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