Keys, Nominals, and Concrete Domains

Carsten Lutz; Carlos Areces; Ian Horrocks; Ulrike Sattler

Journal articles

Keys, Nominals, and Concrete Domains

Carsten Lutz Carlos Areces ¹ Ian Horrocks Ulrike Sattler

1 LANGUE ET DIALOGUE - Human-machine dialogue with a significant language component

INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

Abstract : 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.

Document type :

Journal articles

Complete list of metadata

https://hal.inria.fr/inria-00000294
Contributor : Areces Carlos Connect in order to contact the contributor
Submitted on : Friday, September 23, 2005 - 3:29:43 PM
Last modification on : Friday, February 4, 2022 - 3:29:57 AM

Keys, Nominals, and Concrete Domains

Identifiers

Collections

Citation

Export

Metrics

87

Contact Legal Notice Personal Data

Keys, Nominals, and Concrete Domains

Identifiers

Collections

Citation

Export

Share

Metrics

87

Contact Legal Notice Personal Data