Strong Equivalence in Answer Set Programming with Constraints

• URL: http://arxiv.org/abs/2502.04302v1
• Date: Thu, 06 Feb 2025 18:43:59 GMT
• Title: Strong Equivalence in Answer Set Programming with Constraints
• Authors: Pedro Cabalar, Jorge Fandinno, Torsten Schaub, Philipp Wanko,
• Abstract summary: 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.
• Score: 8.096489007229774
• License:
• Abstract: We investigate the concept of strong equivalence within the extended framework of Answer Set Programming with constraints. Two groups of rules are considered strongly equivalent if, informally speaking, they have the same meaning in any context. We demonstrate that, under certain assumptions, strong equivalence between rule sets in this extended setting can be precisely characterized by their equivalence in the logic of Here-and-There with constraints. Furthermore, 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. This translation enables us to leverage the logic of Here-and-There to reason about strong equivalence within the context of these solvers. We also explore the computational complexity of determining strong equivalence in this context.

Related papers

• A Unified View on Forgetting and Strong Equivalence Notions in Answer Set Programming [14.342696862884704]
  We introduce a novel relativized equivalence notion, which is able to capture all related notions from the literature. We then introduce an operator that combines projection and a relaxation of (SP)-forgetting to obtain the relativized simplifications.
  arXiv  Detail & Related papers  (2023-12-13T09:05:48Z)
• 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)
• Admissibility in Strength-based Argumentation: Complexity and Algorithms (Extended Version with Proofs) [1.5828697880068698]
  We study the adaptation of admissibility-based semantics to Strength-based Argumentation Frameworks (StrAFs) Especially, we show that the strong admissibility defined in the literature does not satisfy a desirable property, namely Dung's fundamental lemma. We propose a translation in pseudo-Boolean constraints for computing (strong and weak) extensions.
  arXiv  Detail & Related papers  (2022-07-05T18:42:04Z)
• Query Answering with Transitive and Linear-Ordered Data [7.879958190837517]
  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.
  arXiv  Detail & Related papers  (2022-02-17T10:00:08Z)
• Composable constraints [0.0]
  We show that every composable constraint encoding can be used to construct an equivalent notion of a constrained category. We show how to express the compatibility of constraints with additional categorical structures of their targets, such as parallel composition, compactness, and time-symmetry.
  arXiv  Detail & Related papers  (2021-12-13T17:24:47Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• Comment on "Strong Quantum Darwinism and Strong Independence are Equivalent to Spectrum Broadcast Structure" [62.997667081978825]
  We show that the mathematical formulation of condition (b) is necessary but not sufficient to ensure the equivalence. We propose a simple counter-example, together with a strengthened formulation of condition (b)
  arXiv  Detail & Related papers  (2021-01-21T16:06:25Z)
• Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
  We give a sound and strongly complete axiomatization that can be parametrized to cover essentially every real-valued logic. Our class of sentences are very rich, and each describes a set of possible real values for a collection of formulas of the real-valued logic.
  arXiv  Detail & Related papers  (2020-08-06T02:13:11Z)
• 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)
• 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)
• An ASP semantics for Constraints involving Conditional Aggregates [9.289905977910378]
  We elaborate upon the formal foundations of hybrid Answer Set Programming (ASP) We extend its underlying logical framework with aggregate functions over constraint values and variables. We put some emphasis on logic programs with linear constraints and show how common ASP aggregates can be regarded as particular cases of so-called conditional linear constraints.
  arXiv  Detail & Related papers  (2020-02-17T12:25:01Z)

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.