LATPub207

PublikationenPublications

• Nach AutorBy Author
• Nach ForschungsgruppeBy Research Group
  • AutomatentheorieAutomata Theory

Toggle side column

NExpTime-complete Description Logics with Concrete Domains

C. LutzC. Lutz

Datei:Lutz-IJCAR.ps.gz

• Download

C. Lutz
NExpTime-complete Description Logics with Concrete Domains
In Rajeev Goré and Alexander Leitsch and Tobias Nipkow, eds., Proceedings of the International Joint Conference on Automated Reasoning, Lecture Notes in Artifical Intelligence, 45-60, 2001. Springer

• Details
• Bibtex

• KurzfassungAbstract
  Concrete domains are an extension of Description Logics (DLs) allowing to

  integrate reasoning about conceptual knowledge with reasoning about ``concrete properties of objects such as sizes, weights, and durations. It is known that reasoning with ALC(D), the basic DL admitting concrete domains, is PSpace-complete. In this paper, it is shown that the upper bound is not robust: we give three examples for seemingly harmless extensions of ALC(D)---namely acyclic TBoxes, inverse roles, and a role-forming concrete domain constructor---that make reasoning NExpTime-hard. As a corresponding upper bound, we show that reasoning with all three extensions together is in

  NExpTime.
• Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ Lutz-IJCAR-01,
  address = {Siena, Italy},
  author = {C. {Lutz}},
  booktitle = {Proceedings of the International Joint Conference on Automated Reasoning},
  editor = {Rajeev {Gor\'e} and Alexander {Leitsch} and Tobias {Nipkow}},
  number = {2083},
  pages = {45--60},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Artifical Intelligence},
  title = {{NExpTime}-complete Description Logics with Concrete Domains},
  year = {2001},
}