Nominal Schemas in Description Logics: Complexities Clarified

Markus KrötzschMarkus Krötzsch, Sebastian RudolphSebastian Rudolph

Download

Markus Krötzsch, Sebastian Rudolph
Nominal Schemas in Description Logics: Complexities Clarified
In Chitta Baral, Giuseppe De Giacomo, Thomas Eiter, eds., Proc. 14th International Conference on Principles of Knowledge Representation and Reasoning (KR'14), 308-317, July 2014. AAAI Press

Details
Bibtex

KurzfassungAbstract
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.
Projekt:Project: DIAMOND
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{KR2014,
  author    = {Markus Kr{\"{o}}tzsch and Sebastian Rudolph},
  title     = {Nominal Schemas in Description Logics: Complexities Clarified},
  editor    = {Chitta Baral and Giuseppe De Giacomo and Thomas Eiter},
  booktitle = {Proc. 14th International Conference on Principles of Knowledge
               Representation and Reasoning (KR'14)},
  publisher = {AAAI Press},
  year      = {2014},
  month     = {July},
  pages     = {308-317}
}