Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

October 22, 2020 · The Ethereal · 🏛 International Conference on Principles of Knowledge Representation and Reasoning

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Pierre Bourhis, Carsten Lutz arXiv ID 2010.11842 Category cs.LO: Logic in CS Cross-listed cs.AI Citations 21 Venue International Conference on Principles of Knowledge Representation and Reasoning Last Checked 2 months ago
Abstract
We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NEXPTIME-completeness and extend this result to monadic disjunctive Datalog and to OMQs.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Logic in CS