Article3065
Complexities of Horn Description Logics
Complexities of Horn Description Logics
Veröffentlicht: 2012
Journal: ACM Transactions on Computational Logic
Bemerkung: to appear
Referierte Veröffentlichung
Kurzfassung
Description Logics (DLs) have become a prominent paradigm for representing knowledge in a variety of application areas. An important factor for this practical success is the ability of DLs to achieve a favourable balance between the expressivity of the logic and the performance of reasoning. Horn description logics (Horn DLs) have attracted attention since their (worst-case) data complexities are in general lower than their overall (i.e., combined) complexities, which makes them attractive for reasoning with large sets of instance data (ABoxes). However, the natural question whether Horn DLs also provide advantages for schema (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 studied herein turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning. We also provide convenient normal forms for defining Horn DLs syntactically.
Semantische Technologien, Beschreibungslogik, Komplexitätstheorie