A tetrachotomy of ontology-mediated queries with a covering axiom
From MaRDI portal
Publication:2152500
DOI10.1016/j.artint.2022.103738OpenAlexW3043797180WikidataQ114016164 ScholiaQ114016164MaRDI QIDQ2152500
Olga Gerasimova, Vladimir V. Podolskii, Agi Kurucz, Stanislav Kikot, Michael Zakharyashchev
Publication date: 8 July 2022
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.04167
description logicDatalogdata complexitydisjunctive Datalogfirst-order rewritabilityontology-mediated query
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
- Towards more expressive ontology languages: the query answering problem
- Colouring, constraint satisfaction, and complexity
- On rules with existential variables: walking the decidability line
- Tractable query answering and rewriting under description logic constraints
- Parallel complexity of logical query programs
- The polynomial-time hierarchy
- On the complexity of single-rule datalog queries.
- Many-dimensional modal logics: theory and applications
- Implementing a test for tractability
- Linearisability on Datalog programs
- Mutilated chessboard problem is exponentially hard for resolution
- Checking the data complexity of ontology-mediated queries: a case study with non-uniform CSPs and Polyanna
- The price of query rewriting in ontology-based data access
- Tractable reasoning and efficient query answering in description logics: The DL-Lite family
- Reasoning in description logics by a reduction to disjunctive datalog
- An Introduction to Description Logic
- Undecidable boundedness problems for datalog programs
- Undecidable optimization problems for database logic programs
- $\mathcal{EL}$ -ifying Ontologies
- PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Homomorphism preservation theorems
- The DL-Lite Family and Relations
- Minimizing function-free recursive inference rules
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
- The parallel complexity of simple logic programs
- PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
- Ontology-Mediated Queries
- The Complexity of Boundedness for Guarded Logics
- Asking the Metaquestions in Constraint Tractability
- Query Rewriting and Optimization for Ontological Databases
- Ontology-Based Data Access
- Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
- The Description Logic Handbook
- Classifying the Complexity of Constraints Using Finite Algebras
- Computational Complexity
- The complexity of satisfiability problems
- Linking Data to Ontologies
- A Characterisation of First-Order Constraint Satisfaction Problems
This page was built for publication: A tetrachotomy of ontology-mediated queries with a covering axiom