The Complexity of Conjunctive Query Answering in Expressive Description Logics

DOI10.1007/978-3-540-71070-7_16zbMath1165.68503OpenAlexW1483388050MaRDI QIDQ3541701

Carsten Lutz

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

Mathematics Subject Classification ID

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

• Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots
• Alternation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Complexity of Conjunctive Query Answering in Expressive Description Logics