A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)

DOI10.1016/J.ARTINT.2022.103709zbMath1495.68211arXiv1904.12533OpenAlexW2940854778MaRDI QIDQ2144172

Leif Sabellek, Carsten Lutz

Publication date: 1 June 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

description logiccomplexity classificationrewritabilitylinear Datalogontology-mediated querying

Mathematics Subject Classification ID

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

Related Items (1)

Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data complexity of query answering in description logics
• Tractable query answering and rewriting under description logic constraints
• CSP duality and trees of bounded pathwidth
• Deciding inseparability and conservative extensions in the description logic
• Alternating automata on infinite trees
• Majority constraints have bounded pathwidth duality
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• Taming the Infinite Chase: Query Answering under Expressive Relational Constraints
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• An Introduction to Description Logic
• Data Complexity in the $\mathcal{EL}$ Family of Description Logics
• Query Answering in the Description Logic Horn- $\mathcal{SHIQ}$
• The Complexity of Conjunctive Query Answering in Expressive Description Logics
• Ontologies and Databases: The DL-Lite Approach
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
• The Complexity of Boundedness for Guarded Logics
• Ontology-Based Data Access
• Linear Datalog and Bounded Path Duality of Relational Structures
• Dualities for Constraint Satisfaction Problems

This page was built for publication: A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)