Keys, Nominals, and Concrete Domains

C. Lutz, C. Areces, I. Horrocks, and U. Sattler. Keys, Nominals, and Concrete Domains. In Eighteenth International Joint Conference on Artificial Intelligence - IJCAI'03, Acapulco, Mexico, pp. 349–354, Acapulco, Mexico, 2003.

Download

[pdf] 

Abstract

Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to `concrete'' domains such as numbers and strings with built-in predicates such as <, +, and prefix-of. These hybrid DLs have turned out to be useful for reasoning about conceptual models of information systems, and as the basis for expressive ontology languages. 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 analyses 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.

BibTeX

@InCollection{Lutz2003,
  author =       "C. Lutz and C. Areces and I. Horrocks and U. Sattler",
  booktitle =    "Eighteenth International Joint Conference on
                 Artificial Intelligence - IJCAI'03, Acapulco, Mexico",
  title =        "Keys, Nominals, and Concrete Domains",
  year =         "2003",
  address =      "Acapulco, Mexico",
  pages =        "349--354",
  abstract =     "Many description logics (DLs) combine knowledge
                 representation on an abstract, logical level with an
                 interface to `concrete'' domains such as numbers and
                 strings with built-in predicates such as <, +, and
                 prefix-of. These hybrid DLs have turned out to be
                 useful for reasoning about conceptual models of
                 information systems, and as the basis for expressive
                 ontology languages. 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 analyses 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.",
  ISBN =         "978-0-12-705661-6",
}