Nominal Schemas in Description Logics: Complexities Clarified

(Redirected from Nominal Schema Complexities)

Markus Krötzsch, Sebastian Rudolph

Nominal Schemas in Description Logics: Complexities Clarified

Abstract. Nominal schemas extend description logics (DLs) with a restricted form of variables, thus integrating rule-like expressive power into standard DLs. They are also one of the most recently introduced DL features, and in spite of many works on algorithms and implementations, almost nothing is known about their computational complexity and expressivity. We close this gap by providing a comprehensive analysis of the reasoning complexities of a wide range of DLs—from EL to SROIQ—extended with nominal schemas. Both combined and data complexities increase by one exponential in most cases, with the one previously known case of SROIQ being the main exception. Our proofs employ general modeling techniques that exploit the power of nominal schemas to succinctly represent many axioms, and which can also be applied to study DLs beyond those we consider. To further improve our understanding of nominal schemas, we also investigate their semantics, traditionally based on finite grounding, and show that it can be extended to infinite sets of individuals without affecting reasoning complexities. We argue that this might be a more suitable semantics when considering entailments of axioms with nominal schemas.

Published at KR 2014 (Conference paper)

Download PDF (last update: 4 Jul 2014)

Citation details

  • Markus Krötzsch, Sebastian Rudolph. Nominal Schemas in Description Logics: Complexities Clarified. In Chitta Baral, Giuseppe De Giacomo, Thomas Eiter, eds.: Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR 2014). AAAI PressProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2014.


You can view the presentation in any modern browser. It was prepared using Sozi and Inkscape; many thanks to these projects.

If you prefer a more static set of slides, please have a look at the talk given at the DL workshop on the same subject.


Description logics