The Complexity of Conjunctive Query Answering in Expressive Description Logics
From MaRDI portal
Publication:3541701
DOI10.1007/978-3-540-71070-7_16zbMath1165.68503OpenAlexW1483388050MaRDI QIDQ3541701
Publication date: 27 November 2008
Published in: Automated Reasoning (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-71070-7_16
Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (12)
A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ Querying the Unary Negation Fragment with Regular Path Expressions. ⋮ Answering regular path queries mediated by unrestricted \(\mathcal{SQ}\) ontologies ⋮ On combining ontologies and rules ⋮ Ontology-Mediated Query Answering with Data-Tractable Description Logics ⋮ Modal definability of first-order formulas with free variables and query answering ⋮ Reasoning and Query Answering in Description Logics ⋮ Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog ⋮ Query Answering in Description Logics: The Knots Approach ⋮ Description Logics ⋮ Query inseparability for \(\mathcal{ALC}\) ontologies ⋮ Logical separability of labeled data examples under ontologies
Cites Work
This page was built for publication: The Complexity of Conjunctive Query Answering in Expressive Description Logics