Query Answering with Transitive and Linear-Ordered Data

• URL: http://arxiv.org/abs/2202.08555v1
• Date: Thu, 17 Feb 2022 10:00:08 GMT
• Title: Query Answering with Transitive and Linear-Ordered Data
• Authors: Antoine Amarilli and Michael Benedikt and Pierre Bourhis and Michael Vanden Boom
• Abstract summary: We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules. We show that slight changes in these conditions lead to undecidability.
• Score: 7.879958190837517
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules in which we impose additional semantic restrictions on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural variants of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in these conditions lead to undecidability.

Related papers

• Mitigating Hallucinations in Multimodal Spatial Relations through Constraint-Aware Prompting [7.962140902232628]
  Spatial relation hallucinations pose a persistent challenge in large vision-language models (LVLMs) We propose a constraint-aware prompting framework designed to reduce spatial relation hallucinations.
  arXiv  Detail & Related papers  (2025-02-12T11:32:19Z)
• Strong Equivalence in Answer Set Programming with Constraints [8.096489007229774]
  Two groups of rules are considered strongly equivalent if, informally speaking, they have the same meaning in any context. We show that strong equivalence can be precisely characterized by their equivalence in the logic of Here-and-There with constraints. We present a translation from the language of several clingo-based answer set solvers that handle constraints into the language of Here-and-There with constraints.
  arXiv  Detail & Related papers  (2025-02-06T18:43:59Z)
• Neuro-Symbolic Rule Lists [31.085257698392354]
  NeuRules is an end-to-end trainable model that unifies discretization, rule learning, and rule order into a single framework. We show that NeuRules consistently outperforms neuro-symbolic methods, effectively learning simple and complex rules, as well as their order, across a wide range of datasets.
  arXiv  Detail & Related papers  (2024-11-10T11:10:36Z)
• On Regularization and Inference with Label Constraints [62.60903248392479]
  We compare two strategies for encoding label constraints in a machine learning pipeline, regularization with constraints and constrained inference. For regularization, we show that it narrows the generalization gap by precluding models that are inconsistent with the constraints. For constrained inference, we show that it reduces the population risk by correcting a model's violation, and hence turns the violation into an advantage.
  arXiv  Detail & Related papers  (2023-07-08T03:39:22Z)
• Relational Sentence Embedding for Flexible Semantic Matching [86.21393054423355]
  We present Sentence Embedding (RSE), a new paradigm to discover further the potential of sentence embeddings. RSE is effective and flexible in modeling sentence relations and outperforms a series of state-of-the-art embedding methods.
  arXiv  Detail & Related papers  (2022-12-17T05:25:17Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Investigating Constraint Relationship in Evolutionary Many-Constraint Optimization [7.383262009823001]
  In a conflicting relationship, the functional value of one constraint increases as the value in another constraint decreases. In an independent relationship, the adjustment to one constraint never affects the adjustment to the other. The transitivity of the relationships is further discussed at the aim of determining the relationship in a new pair of constraints.
  arXiv  Detail & Related papers  (2020-10-09T09:15:08Z)
• Correlations constrained by composite measurements [1.539147548025619]
  How to understand the set of admissible correlations in nature is one outstanding open problem in the core of the foundations of quantum theory. We show that demanding that a theory exhibits a composite measurement imposes a hierarchy of constraints on the structure of its sets of states and effects. In particular, we show that in certain situations this assumption has surprisingly strong consequences, namely, that Tsirelson's bound can be recovered.
  arXiv  Detail & Related papers  (2020-09-10T17:05:19Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Multiplex Word Embeddings for Selectional Preference Acquisition [70.33531759861111]
  We propose a multiplex word embedding model, which can be easily extended according to various relations among words. Our model can effectively distinguish words with respect to different relations without introducing unnecessary sparseness.
  arXiv  Detail & Related papers  (2020-01-09T04:47:14Z)

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.