Keys, Nominals, and Concrete Domains

Carsten LutzCarsten Lutz, C. ArecesC. Areces, Ian HorrocksIan Horrocks, Ulrike SattlerUlrike Sattler

Datei:LutAreHorSat-LTCS-02-04.ps.gz

Download

Carsten Lutz, C. Areces, Ian Horrocks, Ulrike Sattler
Keys, Nominals, and Concrete Domains
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-02-04, 2002. LTCS-Report

Details
Bibtex

KurzfassungAbstract
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 quite 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 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.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ LutAreHorSat-LTCS-02-04,
  address = {Germany},
  author = {C. {Lutz} and C. {Areces} and I. {Horrocks} and U. {Sattler}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {LTCS-02-04},
  title = {Keys, Nominals, and Concrete Domains},
  type = {LTCS-Report},
  year = {2002},
}