Description Logics with Concrete Domains and Functional Dependencies

From International Center for Computational Logic

Toggle side column

Description Logics with Concrete Domains and Functional Dependencies

Carsten LutzCarsten Lutz,  M. MilicicM. Milicic
Carsten Lutz, M. Milicic
Description Logics with Concrete Domains and Functional Dependencies
Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-2004), to appear
  • KurzfassungAbstract
    Description Logics (DLs) with concrete domains are a useful tool in many applications. To further enhance the expressive power of such DLs, it has been proposed to add database-style key constraints. Up to now, however, only uniqueness constraints have been considered in this context, thus neglecting the second fundamental family of key constraints: functional dependencies. In this paper, we consider the basic DL with concrete domains alcd, extend it with functional dependencies, and analyze the impact of this extension on the decidability and complexity of reasoning. Though intuitively the expressivity of functional dependencies seems weaker than that of uniqueness constraints, we are able to show that the former have a similarly severe impact on the computational properties: reasoning is undecidable in the general case, and NExpTime-complete in some slightly restricted variants of our logic.
  • Bemerkung: Note: To appear
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ LutzMilicic-ECAI-2004,
  author = {C. {Lutz} and M. {Milicic}},
  booktitle = {Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-2004)},
  note = {To appear},
  title = {Description Logics with Concrete Domains and Functional Dependencies},
  year = {2004},
}