Keys, Nominals, and Concrete Domains

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

Download: [pdf] 

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.

BibTeX: (download)

@ARTICLE{lutz:keys04,
  author = {Lutz, C. and Areces, C. and Horrocks, I. and Sattler, U.},
  title = {Keys, Nominals, and Concrete Domains},
  journal = {Journal of Artificial Intelligence Research},
  year = {2004},
  volume = {23},
  pages = {667--726},
  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. },
}

Generated by bib2html.pl (written by Patrick Riley) on Sun Oct 02, 2016 17:05:49