Generalizing Level Ranking Constraints for Monotone and Convex Aggregates

• URL: http://arxiv.org/abs/2308.15888v1
• Date: Wed, 30 Aug 2023 09:04:39 GMT
• Title: Generalizing Level Ranking Constraints for Monotone and Convex Aggregates
• Authors: Tomi Janhunen (Tampere University)
• Abstract summary: In answer set programming (ASP), answer sets capture solutions to search problems of interest. One viable implementation strategy is provided by translation-based ASP. We take level ranking constraints into reconsideration, aiming at their generalizations to cover aggregate-based extensions of ASP.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In answer set programming (ASP), answer sets capture solutions to search problems of interest and thus the efficient computation of answer sets is of utmost importance. One viable implementation strategy is provided by translation-based ASP where logic programs are translated into other KR formalisms such as Boolean satisfiability (SAT), SAT modulo theories (SMT), and mixed-integer programming (MIP). Consequently, existing solvers can be harnessed for the computation of answer sets. Many of the existing translations rely on program completion and level rankings to capture the minimality of answer sets and default negation properly. In this work, we take level ranking constraints into reconsideration, aiming at their generalizations to cover aggregate-based extensions of ASP in more systematic way. By applying a number of program transformations, ranking constraints can be rewritten in a general form that preserves the structure of monotone and convex aggregates and thus offers a uniform basis for their incorporation into translation-based ASP. The results open up new possibilities for the implementation of translators and solver pipelines in practice.

Related papers

• Self-Calibrated Listwise Reranking with Large Language Models [137.6557607279876]
  Large language models (LLMs) have been employed in reranking tasks through a sequence-to-sequence approach. This reranking paradigm requires a sliding window strategy to iteratively handle larger candidate sets. We propose a novel self-calibrated listwise reranking method, which aims to leverage LLMs to produce global relevance scores for ranking.
  arXiv  Detail & Related papers  (2024-11-07T10:31:31Z)
• Probabilistic and Causal Satisfiability: the Impact of Marginalization [3.44747819522562]
  We focus on satisfiability problems expressed in probabilistic and causal languages. We show that linear languages (allowing addition and marginalization) yield NPPP-, PSPACE-, and NEXP-complete satisfiability problems. We also consider constrained models that are restricted to a given Bayesian network, a Directed Acyclic Graph structure, or a small size.
  arXiv  Detail & Related papers  (2024-05-12T20:25:36Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• From Instructions to Constraints: Language Model Alignment with Automatic Constraint Verification [70.08146540745877]
  We investigate common constraints in NLP tasks, categorize them into three classes based on the types of their arguments. We propose a unified framework, ACT (Aligning to ConsTraints), to automatically produce supervision signals for user alignment with constraints.
  arXiv  Detail & Related papers  (2024-03-10T22:14:54Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  We characterize several different forms of compositional generalization that are desirable in program synthesis. We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
  arXiv  Detail & Related papers  (2023-07-26T01:07:52Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  Recent works leverage the capabilities of large language models (LMs) to perform complex question answering in a few-shot setting. We introduce Successive Prompting'', where we iteratively break down a complex task into a simple task, solve it, and then repeat the process until we get the final solution. Our best model (with successive prompting) achieves an improvement of 5% absolute F1 on a few-shot version of the DROP dataset.
  arXiv  Detail & Related papers  (2022-12-08T06:03:38Z)
• Grounded Graph Decoding Improves Compositional Generalization in Question Answering [68.72605660152101]
  Question answering models struggle to generalize to novel compositions of training patterns, such as longer sequences or more complex test structures. We propose Grounded Graph Decoding, a method to improve compositional generalization of language representations by grounding structured predictions with an attention mechanism. Our model significantly outperforms state-of-the-art baselines on the Compositional Freebase Questions (CFQ) dataset, a challenging benchmark for compositional generalization in question answering.
  arXiv  Detail & Related papers  (2021-11-05T17:50:14Z)
• Aggregate Semantics for Propositional Answer Set Programs [14.135212040150389]
  We present and compare the main aggregate semantics that have been proposed for propositional ASP programs. We highlight crucial properties such as computational complexity and expressive power, and outline the capabilities and limitations of different approaches.
  arXiv  Detail & Related papers  (2021-09-17T17:38:55Z)
• Planning with Incomplete Information in Quantified Answer Set Programming [1.3501640559999886]
  We present a general approach to planning with incomplete information in Answer Set Programming (ASP) We represent planning problems using a simple formalism where logic programs describe the transition function between states. We present a translation-based QASP solver that converts quantified logic programs into QBFs and then executes a QBF solver.
  arXiv  Detail & Related papers  (2021-08-13T21:24:47Z)
• 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)
• Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
  Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) We show that central problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds.
  arXiv  Detail & Related papers  (2020-01-13T13:16:13Z)

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.