How to tell easy from hard: complexities of conjunctive query entailment in extensions of ALC

DOI10.1613/JAIR.1.14482MaRDI QIDQ6535408zbMATH OpenFDO

Authors Bartosz Bednarczyk, Sebastian Rudolph

Publication date 20 December 2023

Published in The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/JAIR.1.14482

zbMATH Keywords

automated reasoningdatabasesdescription logicsintelligent databasesquery

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Knowledge representation (68T30)

Recommendations

• The Complexity of Conjunctive Query Answering in Expressive Description Logics
• Complexity of Default Logic on Generalized Conjunctive Queries
• On the complexity of entailment in propositional multivalued logics
• How hard is completeness reasoning for conjunctive queries?
• On the complexity of entailment in existential conjunctive first-order logic with atomic negation
• Theory and Applications of Satisfiability Testing
• Parameterized complexity of completeness reasoning for conjunctive queries
• Combined-semantics equivalence of conjunctive queries: decidability and tractability results

Cites work

• A new description logic with set constraints and cardinality constraints on role successors
• Alternation
• An introduction to description logic
• Answering regular path queries in expressive description logics via alternating tree-automata
• Coalgebraic Reasoning with Global Assumptions in Arithmetic Modal Logics
• Complexity of modal logics with Presburger constraints
• Conjunctive query answering for the description logic SHIQ
• Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots
• Decision procedures and expressiveness in the temporal logic of branching time
• Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment
• Guarded negation
• scientific article; zbMATH DE number 67503 (Why is no real title available?)
• scientific article; zbMATH DE number 1149440 (Why is no real title available?)
• scientific article; zbMATH DE number 1936671 (Why is no real title available?)
• Modal and guarded characterisation theorems over finite transition systems
• Modal languages and bounded fragments of predicate logic
• On the Restraining Power of Guards
• Querying the Guarded Fragment
• Reasoning and query answering in description logics
• Satisfiability and query answering in description logics with global and local cardinality constraints
• The Complexity of Conjunctive Query Answering in Expressive Description Logics
• The Complexity of Enriched Mu-Calculi
• Towards Efficient Satisfiability Checking for Boolean Algebra with Presburger Arithmetic
• Towards Statistical Reasoning in Description Logics over Finite Domains

Cited in

(2)

• How hard is completeness reasoning for conjunctive queries?
• Decidability of querying first-order theories via countermodels of finite width

This page was built for publication: How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535408)