Complexity of Arithmetic in Warded Datalog+-

• URL: http://arxiv.org/abs/2202.05086v1
• Date: Thu, 10 Feb 2022 15:14:03 GMT
• Title: Complexity of Arithmetic in Warded Datalog+-
• Authors: Lucas Berent, Markus Nissl, Emanuel Sallinger
• Abstract summary: Warded Datalog+- extends the logic-based language Datalog with existential quantifiers in rule heads. We define a new language that extends Warded Datalog+- with arithmetic and prove its P-completeness. We present an efficient reasoning algorithm for our newly defined language and prove descriptive complexity for a recently introduced Datalog fragment with integer arithmetic.
• Score: 1.5469452301122173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Warded Datalog+- extends the logic-based language Datalog with existential quantifiers in rule heads. Existential rules are needed for advanced reasoning tasks, e.g., ontological reasoning. The theoretical efficiency guarantees of Warded Datalog+- do not cover extensions crucial for data analytics, such as arithmetic. Moreover, despite the significance of arithmetic for common data analytic scenarios, no decidable fragment of any Datalog+- language extended with arithmetic has been identified. We close this gap by defining a new language that extends Warded Datalog+- with arithmetic and prove its P-completeness. Furthermore, we present an efficient reasoning algorithm for our newly defined language and prove descriptive complexity results for a recently introduced Datalog fragment with integer arithmetic, thereby closing an open question. We lay the theoretical foundation for highly expressive Datalog+- languages that combine the power of advanced recursive rules and arithmetic while guaranteeing efficient reasoning algorithms for applications in modern AI systems, such as Knowledge Graphs.

Related papers

• Discovering symbolic expressions with parallelized tree search [59.92040079807524]
  Symbolic regression plays a crucial role in scientific research thanks to its capability of discovering concise and interpretable mathematical expressions from data. Existing algorithms have faced a critical bottleneck of accuracy and efficiency over a decade when handling problems of complexity. We introduce a parallelized tree search (PTS) model to efficiently distill generic mathematical expressions from limited data.
  arXiv  Detail & Related papers  (2024-07-05T10:41:15Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a complex reasoning schema over KG upon large language models (LLMs) We augment the arbitrary first-order logical queries via binary tree decomposition to stimulate the reasoning capability of LLMs. Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• Fuzzy Datalog$^\exists$ over Arbitrary t-Norms [5.464669506214195]
  One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data. This requires combining heterogeneous data sources such as knowledge graphs, neural model predictions, structured databases, crowd-sourced data, and many more. We generalise the standard rule-based language Datalog with existential rules to the setting, by allowing for arbitrary t-norms in the place of classical conjunctions in rule bodies. The resulting formalism allows us to perform reasoning about associated data with degrees of uncertainty while preserving computational complexity results and the applicability of reasoning techniques established for
  arXiv  Detail & Related papers  (2024-03-05T12:51:40Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• Enhancing Datalog Reasoning with Hypertree Decompositions [17.868595375154506]
  We provide algorithms that exploit hypertree decompositions for the materialisation and incremental evaluation of Datalog programs. We combine this approach with standard Datalog reasoning algorithms in a modular fashion so that the overhead caused by the decompositions is reduced.
  arXiv  Detail & Related papers  (2023-05-11T14:51:16Z)
• Seminaive Materialisation in DatalogMTL [10.850687097496373]
  DatalogMTL is an extension of Datalog with metric temporal operators. We propose a materialisation-based procedure to minimise redundant computation. Our experiments show that our optimised seminaive strategy for DatalogMTL is able to significantly reduce materialisation times.
  arXiv  Detail & Related papers  (2022-08-15T10:04:44Z)
• 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)
• Logic-Driven Context Extension and Data Augmentation for Logical Reasoning of Text [65.24325614642223]
  We propose to understand logical symbols and expressions in the text to arrive at the answer. Based on such logical information, we put forward a context extension framework and a data augmentation algorithm. Our method achieves the state-of-the-art performance, and both logic-driven context extension framework and data augmentation algorithm can help improve the accuracy.
  arXiv  Detail & Related papers  (2021-05-08T10:09:36Z)
• iWarded: A System for Benchmarking Datalog+/- Reasoning (technical report) [0.0]
  iWarded is a system that can generate very large, complex, realistic reasoning settings. We present the iWarded system and a set of novel theoretical results adopted to generate effective scenarios.
  arXiv  Detail & Related papers  (2021-03-15T17:56:46Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  We extend implicit learning in PAC-Semantics to handle intervals and threshold uncertainty in the language of linear arithmetic. We show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.
  arXiv  Detail & Related papers  (2020-10-23T19:08:46Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  We study the task of logical generalization using graph neural networks (GNNs) Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics. We find that the ability for models to generalize and adapt is strongly determined by the diversity of the logical rules they encounter during training.
  arXiv  Detail & Related papers  (2020-03-14T05:45:55Z)

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.