A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
From MaRDI portal
Publication:2144172
DOI10.1016/j.artint.2022.103709zbMath1495.68211arXiv1904.12533OpenAlexW2940854778MaRDI QIDQ2144172
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
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Logic in artificial intelligence (68T27) Knowledge representation (68T30)
Related Items (1)
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}\)
