Complexity of Horn Description Logics

Markus KrötzschMarkus Krötzsch, Pascal HitzlerPascal Hitzler, Sebastian RudolphSebastian Rudolph

Markus Krötzsch, Pascal Hitzler, Sebastian Rudolph
Complexity of Horn Description Logics
Technical Report, Instistute AIFB, Universität Karlsruhe, volume 1432, February 2007

Details
Bibtex

KurzfassungAbstract
Horn description logics (Horn-DLs) have recently started to attract attention
due to the fact that their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large ABoxes. However, the natural question whether Horn-DLs also provide advantages for TBox reasoning has hardly been addressed so far. In this paper, we therefore provide a thorough and comprehensive analysis of the combined complexities of Horn-DLs. While the combined complexity for many Horn-DLs turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness
simplifies reasoning.
Weitere Informationen unter:Further Information: Link
Projekt:Project: ReaSem
Forschungsgruppe:Research Group: Information Systems„Information Systems“ befindet sich nicht in der Liste (Computational Logic, Automatentheorie, Wissensverarbeitung, Knowledge-Based Systems, Knowledge Systems, Wissensbasierte Systeme, Logische Programmierung und Argumentation, Algebra und Diskrete Strukturen, Knowledge-aware Artificial Intelligence, Algebraische und logische Grundlagen der Informatik) zulässiger Werte für das Attribut „Forschungsgruppe“.Knowledge-Based Systems

@techreport{KHR2007,
  author      = {Markus Kr{\"{o}}tzsch and Pascal Hitzler and Sebastian Rudolph},
  title       = {Complexity of Horn Description Logics},
  institution = {Instistute {AIFB,} Universit{\"{a}}t Karlsruhe},
  year        = {2007},
  month       = {February}
}