Nominal Schemas in Description Logics: Complexities Clarified
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
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 εL 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.
Details
Original language | English |
---|---|
Title of host publication | Proceedings of the Fourteenth International Conference On Principles of Knowledge Representation and Reasoning |
Pages | 308-317 |
Volume | 2 |
Publication status | Published - 2014 |
Peer-reviewed | Yes |
Publication series
Series | Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning |
---|---|
ISSN | 2334-1025 |
External IDs
researchoutputwizard | legacy.publication#68926 |
---|---|
Scopus | 84962068259 |