Normalisations of Existential Rules: Not so Innocuous!

• URL: http://arxiv.org/abs/2206.03124v1
• Date: Tue, 7 Jun 2022 09:01:56 GMT
• Title: Normalisations of Existential Rules: Not so Innocuous!
• Authors: David Carral, Lucas Larroque, Marie-Laure Mugnier and Micha\"el Thomazo
• Abstract summary: We study the impact of Existential Rules on chase variants with respect to chase (non-)termination and FO-rewritability. This also leads us to study open problems related to chase termination of independent interest.
• Score: 7.260554897161947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existential rules are an expressive knowledge representation language mainly developed to query data. In the literature, they are often supposed to be in some normal form that simplifies technical developments. For instance, a common assumption is that rule heads are atomic, i.e., restricted to a single atom. Such assumptions are considered to be made without loss of generality as long as all sets of rules can be normalised while preserving entailment. However, an important question is whether the properties that ensure the decidability of reasoning are preserved as well. We provide a systematic study of the impact of these procedures on the different chase variants with respect to chase (non-)termination and FO-rewritability. This also leads us to study open problems related to chase termination of independent interest.

Related papers

• Beyond the Projection Postulate and Back: Quantum Theories with Generalised State-Update Rules [0.0]
  Explicit examples of valid unconventional update rules are presented.<n>This framework of state-update rules allows us to identify operational properties that distinguish the projective update rule from all others.
  arXiv  Detail & Related papers  (2025-06-06T16:12:59Z)
• On Principles and Representations for Extended Contextuality [6.567540943027728]
  Dzhafarov and Kujala: If standard contextuality satisfies some principle that extended contextuality does not, then that principle must be non-substantive' in that it depends on a superficial choice of representation. This paper raises several objections to their argument, including that it neglects how substantive principles change their expression under a change of representation.
  arXiv  Detail & Related papers  (2024-10-08T06:39:49Z)
• Faithful Differentiable Reasoning with Reshuffled Region-based Embeddings [62.93577376960498]
  Knowledge graph embedding methods learn geometric representations of entities and relations to predict plausible missing knowledge.<n>We propose RESHUFFLE, a model based on ordering constraints that can faithfully capture a much larger class of rule bases.<n>The entity embeddings in our framework can be learned by a Graph Neural Network (GNN), which effectively acts as a differentiable rule base.
  arXiv  Detail & Related papers  (2024-06-13T18:37:24Z)
• Are language models rational? The case of coherence norms and belief revision [63.78798769882708]
  We consider logical coherence norms as well as coherence norms tied to the strength of belief in language models. We argue that rational norms tied to coherence do apply to some language models, but not to others.
  arXiv  Detail & Related papers  (2024-06-05T16:36:21Z)
• Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement [92.61557711360652]
  Language models (LMs) often fall short on inductive reasoning, despite achieving impressive success on research benchmarks. We conduct a systematic study of the inductive reasoning capabilities of LMs through iterative hypothesis refinement. We reveal several discrepancies between the inductive reasoning processes of LMs and humans, shedding light on both the potentials and limitations of using LMs in inductive reasoning tasks.
  arXiv  Detail & Related papers  (2023-10-12T17:51:10Z)
• Causality Inspired Representation Learning for Domain Generalization [47.574964496891404]
  We introduce a general structural causal model to formalize the Domain generalization problem. Our goal is to extract the causal factors from inputs and then reconstruct the invariant causal mechanisms. We highlight that ideal causal factors should meet three basic properties: separated from the non-causal ones, jointly independent, and causally sufficient for the classification.
  arXiv  Detail & Related papers  (2022-03-27T08:08:33Z)
• Parallelisable Existential Rules: a Story of Pieces [2.20439695290991]
  We introduce parallelisable sets of existential rules, for which the chase can be computed in a single breadth-first step from any instance. We show that parallelisable rule sets are exactly those rule sets both bounded for the chase and belonging to a novel class of rules, called pieceful.
  arXiv  Detail & Related papers  (2021-07-13T13:09:14Z)
• Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization [77.24152933825238]
  We show that for linear classification tasks we need stronger restrictions on the distribution shifts, or otherwise OOD generalization is impossible. We prove that a form of the information bottleneck constraint along with invariance helps address key failures when invariant features capture all the information about the label and also retains the existing success when they do not.
  arXiv  Detail & Related papers  (2021-06-11T20:42:27Z)
• Transitional Conditional Independence [0.0]
  We introduce transition probability spaces and transitional random variables. These constructions will generalize, strengthen and previous notions of (conditional) random variables and non-stochastic variables.
  arXiv  Detail & Related papers  (2021-04-23T11:52:15Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Oblivious and Semi-Oblivious Boundedness for Existential Rules [5.875276459237496]
  We study the notion of boundedness in the context of positive existential rules. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem.
  arXiv  Detail & Related papers  (2020-06-15T15:18:57Z)
• Characterizing Boundedness in Chase Variants [1.7033055327465234]
  We investigate the decidability of the k-boundedness problem, which asks whether the depth of the chase for a given set of rules is bounded by an integer k. We show that the main chase variants satisfy this property, namely the oblivious, semi-oblivious, and restricted chase, as well as their breadth-first versions.
  arXiv  Detail & Related papers  (2020-04-21T14:07:10Z)

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.