The data complexity of description logic ontologies

DOI10.23638/LMCS-13(4:7)2017MaRDI QIDQ4596784zbMATH OpenFDO

Authors Carsten Lutz, F. Wolter

Publication date 11 December 2017

Full work available at URL https://arxiv.org/abs/1611.02453

zbMATH Keywords

description logicdata complexityontology-mediated querying

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Logic in artificial intelligence (68T27)

Recommendations

• The data complexity of ontology-mediated queries with closed predicates
• Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• Data complexity of query answering in description logics
• Data complexity of query answering in expressive description logics via tableaux

Cited in

(11)

• Datalog rewritability and data complexity of \(\mathcal{ALCHOIQ}\) with closed predicates
• First-order rewritability of ontology-mediated queries in linear temporal logic
• Data complexity of query answering in expressive description logics via tableaux
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• The data complexity of ontology-mediated queries with closed predicates
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• Query answering with DBoxes is hard
• Checking the data complexity of ontology-mediated queries: a case study with non-uniform CSPs and Polyanna
• On the Complexity of Learning Description Logic Ontologies
• When is ontology-mediated querying efficient?
• Horn knowledge bases in regular description logics with PTime data complexity

This page was built for publication: The data complexity of description logic ontologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596784)