Nominal Schemas in Description Logics: Complexities Clarified
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.
author = {Markus Kr{\"o}tzsch and Sebastian Rudolph},
title = {Nominal Schemas in Description Logics:
Complexities Clarified},
booktitle = {Proceedings of the 14th International Conference
on Principles of Knowledge Representation and
Reasoning (KR'14)},
editor = {Chitta Baral and Giuseppe {De Giacomo} and
Thomas Eiter},
year = {2014},
publisher = {AAAI Press}
}
Remarks
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.
