A Unified View on Forgetting and Strong Equivalence Notions in Answer Set Programming

• URL: http://arxiv.org/abs/2312.07993v1
• Date: Wed, 13 Dec 2023 09:05:48 GMT
• Title: A Unified View on Forgetting and Strong Equivalence Notions in Answer Set Programming
• Authors: Zeynep G. Saribatur and Stefan Woltran
• Abstract summary: 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.
• Score: 14.342696862884704
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answer Set Programming (ASP) is a prominent rule-based language for knowledge representation and reasoning with roots in logic programming and non-monotonic reasoning. The aim to capture the essence of removing (ir)relevant details in ASP programs led to the investigation of different notions, from strong persistence (SP) forgetting, to faithful abstractions, and, recently, strong simplifications, where the latter two can be seen as relaxed and strengthened notions of forgetting, respectively. Although it was observed that these notions are related, especially given that they have characterizations through the semantics for strong equivalence, it remained unclear whether they can be brought together. In this work, we bridge this gap by introducing a novel relativized equivalence notion, which is a relaxation of the recent simplification notion, that is able to capture all related notions from the literature. We provide necessary and sufficient conditions for relativized simplifiability, which shows that the challenging part is for when the context programs do not contain all the atoms to remove. We then introduce an operator that combines projection and a relaxation of (SP)-forgetting to obtain the relativized simplifications. We furthermore present complexity results that complete the overall picture.

Related papers

• Rethinking State Disentanglement in Causal Reinforcement Learning [78.12976579620165]
  Causality provides rigorous theoretical support for ensuring that the underlying states can be uniquely recovered through identifiability. We revisit this research line and find that incorporating RL-specific context can reduce unnecessary assumptions in previous identifiability analyses for latent states. We propose a novel approach for general partially observable Markov Decision Processes (POMDPs) by replacing the complicated structural constraints in previous methods with two simple constraints for transition and reward preservation.
  arXiv  Detail & Related papers  (2024-08-24T06:49:13Z)
• Learning Visual-Semantic Subspace Representations for Propositional Reasoning [49.17165360280794]
  We propose a novel approach for learning visual representations that conform to a specified semantic structure. Our approach is based on a new nuclear norm-based loss. We show that its minimum encodes the spectral geometry of the semantics in a subspace lattice.
  arXiv  Detail & Related papers  (2024-05-25T12:51:38Z)
• Transitivity Recovering Decompositions: Interpretable and Robust Fine-Grained Relationships [69.04014445666142]
  Transitivity Recovering Decompositions (TRD) is a graph-space search algorithm that identifies interpretable equivalents of abstract emergent relationships. We show that TRD is provably robust to noisy views, with empirical evidence also supporting this finding.
  arXiv  Detail & Related papers  (2023-10-24T16:48:56Z)
• Discourse-Aware Text Simplification: From Complex Sentences to Linked Propositions [11.335080241393191]
  Text Simplification (TS) aims to modify sentences in order to make them easier to process. We present a discourse-aware TS approach that splits and rephrases complex English sentences. We generate a semantic hierarchy of minimal propositions that puts a semantic layer on top of the simplified sentences.
  arXiv  Detail & Related papers  (2023-08-01T10:10:59Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• 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)
• Rationale-Augmented Ensembles in Language Models [53.45015291520658]
  We reconsider rationale-augmented prompting for few-shot in-context learning. We identify rationale sampling in the output space as the key component to robustly improve performance. We demonstrate that rationale-augmented ensembles achieve more accurate and interpretable results than existing prompting approaches.
  arXiv  Detail & Related papers  (2022-07-02T06:20:57Z)
• Quantification and Aggregation over Concepts of the Ontology [0.0]
  We argue that in some KR applications, we want to quantify over sets of concepts formally represented by symbols in the vocabulary. We present an extension of first-order logic to support such abstractions, and show that it allows writing expressions of knowledge that are elaboration tolerant.
  arXiv  Detail & Related papers  (2022-02-02T07:49:23Z)
• Analyzing Semantics of Aggregate Answer Set Programming Using Approximation Fixpoint Theory [1.295566630218982]
  We introduce the notion of a ternary satisfaction relation and define stable semantics in terms of it. We show that ternary satisfaction relations bridge the gap between the standard Gelfond-Lifschitz reduct, and stable semantics as defined in the framework of AFT.
  arXiv  Detail & Related papers  (2021-04-30T07:06:27Z)
• Discrete Reasoning Templates for Natural Language Understanding [79.07883990966077]
  We present an approach that reasons about complex questions by decomposing them to simpler subquestions. We derive the final answer according to instructions in a predefined reasoning template. We show that our approach is competitive with the state-of-the-art while being interpretable and requires little supervision.
  arXiv  Detail & Related papers  (2021-04-05T18:56:56Z)
• Constraint Monotonicity, Epistemic Splitting and Foundedness Could in General Be Too Strong in Answer Set Programming [32.60523531309687]
  We consider the notions of subjective constraint monotonicity, epistemic splitting, and foundedness as main criteria respectively intuitions to compare different answer set semantics. In this note, we demonstrate on some examples that they may be too strong in general and may exclude some desired answer sets respectively world views.
  arXiv  Detail & Related papers  (2020-10-01T04:03:11Z)

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.