Keys, Nominals, and Concrete Domains

C. LutzC. Lutz, C. ArecesC. Areces, I. HorrocksI. Horrocks, U. SattlerU. Sattler

Datei:LuArHoSaJAIR04.ps.gz

Download

C. Lutz, C. Areces, I. Horrocks, U. Sattler
Keys, Nominals, and Concrete Domains
Journal of Artificial Intelligence Research, 23:667--726, 2005

Details
Bibtex

KurzfassungAbstract
Many description logics (DLs) combine knowledge representation on an
abstract, logical level with an interface to "concrete" domains like numbers and strings with built-in predicates such as <, +, and prefix-of. These hybrid DLs have turned out to be useful in several application areas, such as reasoning about conceptual database models. We propose to further extend such DLs with key
```
 constraints that allow the expression of statements like "US
```
citizens are uniquely identified by their social security number". Based on this idea, we introduce a number of natural description logics and perform a detailed analysis of their decidability and computational complexity. It turns out that naive extensions with key constraints easily lead to undecidability, whereas more careful extensions yield NExpTime-complete DLs for a variety of useful
concrete domains.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ LuArHoSaJAIR05,
  author = {C. {Lutz} and C. {Areces} and I. {Horrocks} and U. {Sattler}},
  journal = {Journal of Artificial Intelligence Research},
  pages = {667--726},
  title = {Keys, Nominals, and Concrete Domains},
  volume = {23},
  year = {2005},
}