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

• URL: http://arxiv.org/abs/2010.11842v1
• Date: Thu, 22 Oct 2020 16:25:00 GMT
• Title: Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
• Authors: Pierre Bourhis and Carsten Lutz
• Abstract summary: 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) We prove 2NEXPTIME-completeness and extend this result to monadic disjunctive Datalog and to OMQs.
• Score: 17.17606390337468
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Data Complexity in Expressive Description Logics With Path Expressions [7.832189413179361]
  We investigate the data complexity of the satisfiability problem for the expressive description logic ZOIQ (a.k.a. ALCHb Self reg OIQ) over quasi-forests. This completes the data complexity landscape for decidable fragments of ZOIQ, and reproves known results on decidable fragments of OWL2 (SR family)
  arXiv  Detail & Related papers  (2024-06-11T09:37:51Z)
• Neuro-Symbolic Integration Brings Causal and Reliable Reasoning Proofs [95.07757789781213]
  Two lines of approaches are adopted for complex reasoning with LLMs. One line of work prompts LLMs with various reasoning structures, while the structural outputs can be naturally regarded as intermediate reasoning steps. The other line of work adopt LLM-free declarative solvers to do the reasoning task, rendering higher reasoning accuracy but lacking interpretability due to the black-box nature of the solvers. We present a simple extension to the latter line of work. Specifically, we showcase that the intermediate search logs generated by Prolog interpreters can be accessed and interpreted into human-readable reasoning.
  arXiv  Detail & Related papers  (2023-11-16T11:26:21Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation [102.20036684996248]
  We propose MURMUR, a neuro-symbolic modular approach to text generation from semi-structured data with multi-step reasoning. We conduct experiments on two data-to-text generation tasks like WebNLG and LogicNLG.
  arXiv  Detail & Related papers  (2022-12-16T17:36:23Z)
• Maieutic Prompting: Logically Consistent Reasoning with Recursive Explanations [71.2950434944196]
  We develop Maieutic Prompting, which infers a correct answer to a question even from the noisy and inconsistent generations of language models. Maieutic Prompting achieves up to 20% better accuracy than state-of-the-art prompting methods.
  arXiv  Detail & Related papers  (2022-05-24T06:36:42Z)
• LogicSolver: Towards Interpretable Math Word Problem Solving with Logical Prompt-enhanced Learning [135.8654475934613]
  We first construct a high-quality MWP dataset named InterMWP which consists of 11,495 MWPs. We propose a novel approach with logical prompt and interpretation, called Logicr. With these improved semantic representations, our Logicr generates corresponding solution expressions and interpretable knowledge in accord with the generated solution expressions.
  arXiv  Detail & Related papers  (2022-05-17T11:01:52Z)
• On the Relationship between Shy and Warded Datalog+/- [3.4696964555947694]
  DatalogE is the extension of Datalog with existential quantification. It is suitable for modern applications on knowledge graphs, query answering (QA) over such language is known to be undecidable in general. Different fragments have emerged, introducing syntactic limitations to DatalogE that strike a balance between its expressive power and the computational complexity of QA.
  arXiv  Detail & Related papers  (2022-02-13T11:24:22Z)
• From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying [17.79631575141597]
  We consider ontology-mediated queries based on expressive description logics of the ALC family and (unions) of conjunctive queries. Our results include exact characterizations of when such a rewriting is possible and tight complexity bounds for deciding rewritability.
  arXiv  Detail & Related papers  (2020-10-22T16:40:59Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries. We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups) Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
  arXiv  Detail & Related papers  (2020-06-07T14:47:07Z)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  We study the evaluation of ontology-mediated queries over relational databases. We provide a characterization of the classes of OMQs that are tractable in combined complexity. We also study the complexity of deciding whether a given OMQ is equivalent to an OMQ of bounded tree width.
  arXiv  Detail & Related papers  (2020-03-17T16:32:00Z)
• VQA-LOL: Visual Question Answering under the Lens of Logic [58.30291671877342]
  We investigate whether visual question answering systems trained to answer a question about an image, are able to answer the logical composition of multiple such questions. We construct an augmentation of the VQA dataset as a benchmark, with questions containing logical compositions and linguistic transformations. We propose our Lens of Logic (LOL) model which uses question-attention and logic-attention to understand logical connectives in the question, and a novel Fr'echet-Compatibility Loss.
  arXiv  Detail & Related papers  (2020-02-19T17:57:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.