Description Logics with Concrete Domains and Functional Dependencies

C. LutzC. Lutz, M. MilicicM. Milicic

Datei:LutzMilicic-ECAI-2004.ps.gz

Download

C. Lutz, M. Milicic
Description Logics with Concrete Domains and Functional Dependencies
Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-2004), to appear

Details
Bibtex

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