EUVIMEDEUVIMED entdecken
Crossref

Complexities of Horn Description Logics

Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler

ACM Transactions on Computational Logic · 2013-02 · 14 (1) · 1-36

DOI: 10.1145/2422085.2422087 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, 2013-02. Verfasst von Markus Krötzsch und 2 weiteren Autor:innen. Die Arbeit wurde bisher 31-mal zitiert (Crossref) und nennt 41 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft, Engineering and Physical Sciences Research Council, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Description logics (DLs) have become a prominent paradigm for representing knowledge in a variety of application areas, partly due to their ability to achieve a favourable balance between expressivity of the logic and performance of reasoning. Horn description logics are obtained, roughly speaking, by disallowing all forms of disjunctions. They have attracted attention since their (worst-case) data complexities are in general lower than those of their non-Horn counterparts, which makes them attractive for reasoning with large sets of instance data (ABoxes). It is therefore natural to ask whether Horn DLs also provide advantages for schema (TBox) reasoning, that is, whether they also feature lower combined complexities. This article settles this question for a variety of Horn DLs. An example of a tractable Horn logic is the DL underlying the ontology language OWL RL, which we characterize as the Horn fragment of the description logic SROIQ without existential quantifiers. If existential quantifiers are allowed, however, many Horn DLs become intractable. We find that Horn- ALC already has the same worst-case complexity as ALC , that is, ExpTime , but we also identify various DLs for which reasoning is PSpace -complete. As a side effect, we derive simplified syntactic definitions of Horn DLs for which we exploit suitable normal form transformations.

Förderung

  • Deutsche Forschungsgemeinschaft
  • Engineering and Physical Sciences Research Council
  • National Science Foundation

Zitieren

APA

Krötzsch, M., Rudolph, S., & Hitzler, P. (2013). Complexities of Horn Description Logics. ACM Transactions on Computational Logic, 14(1), 1-36. https://doi.org/10.1145/2422085.2422087

Vancouver

Krötzsch M, Rudolph S, Hitzler P. Complexities of Horn Description Logics. ACM Transactions on Computational Logic. 2013;14(1):1-36. doi:10.1145/2422085.2422087

BibTeX
@article{Krtzsch2013,
  author = {Krötzsch, Markus and Rudolph, Sebastian and Hitzler, Pascal},
  title = {Complexities of Horn Description Logics},
  journal = {ACM Transactions on Computational Logic},
  year = {2013},
  volume = {14},
  number = {1},
  pages = {1--36},
  doi = {10.1145/2422085.2422087}
}
Kostenlos starten →