Data complexity of query answering in expressive description logics via tableaux

DOI10.1007/s10817-008-9102-9zbMath1154.68102OpenAlexW2135109168WikidataQ64360078 ScholiaQ64360078MaRDI QIDQ945056

Magdalena Ortiz, Diego Calvanese, Thomas Eiter

Publication date: 10 September 2008

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10817-008-9102-9

zbMATH Keywords

data complexityquery answeringexpressive description logics

Mathematics Subject Classification ID

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

Related Items (16)

Data-complexity of the two-variable fragment with counting quantifiers ⋮ Unnamed Item ⋮ View-based query answering in description logics: semantics and complexity ⋮ Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots ⋮ Ontology-Mediated Query Answering with Data-Tractable Description Logics ⋮ Tractable reasoning and efficient query answering in description logics: The DL-Lite family ⋮ Reasoning and Query Answering in Description Logics ⋮ Answering regular path queries in expressive description logics via alternating tree-automata ⋮ Tractability and intractability of controlled languages for data access ⋮ Linking Data to Ontologies ⋮ Query Answering in Description Logics: The Knots Approach ⋮ Description Logics ⋮ Ontologies and Databases: The DL-Lite Approach ⋮ Query Answering with DBoxes is Hard ⋮ Exploiting conjunctive queries in description logic programs ⋮ Hybrid Logics and Ontology Languages

Uses Software

• FaCT++
• Racer
• KL-ONE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data complexity of query answering in description logics
• A resolution-based decision procedure for \({\mathcal{SHOIQ}}\).
• Combining Horn rules and description logics in CARIN
• Combining deduction and model checking into tableaux and algorithms for converse-PDL.
• Reasoning on UML class diagrams
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• A tableau decision procedure for \(\mathcal{SHOIQ}\)
• PSPACE Reasoning for Graded Modal Logics
• Conjunctive queries over trees
• Optimized Reasoning in Description Logics Using Hypertableaux
• Deduction in Concept Languages: from Subsumption to Instance Checking
• Logic for Programming, Artificial Intelligence, and Reasoning
• An overview of tableau algorithms for description logics

This page was built for publication: Data complexity of query answering in expressive description logics via tableaux