LP2PB: Translating Answer Set Programs into Pseudo-Boolean Theories

• URL: http://arxiv.org/abs/2009.10248v1
• Date: Tue, 22 Sep 2020 00:50:17 GMT
• Title: LP2PB: Translating Answer Set Programs into Pseudo-Boolean Theories
• Authors: Wolf De Wulf (Vrije Universiteit Brussel), Bart Bogaerts (Vrije Universiteit Brussel)
• Abstract summary: We present a new tool LP2PB that translates ASP programs into pseudo-Boolean theories. We evaluate our tool, and the potential of cutting-plane-based solving for ASP on traditional ASP benchmarks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answer set programming (ASP) is a well-established knowledge representation formalism. Most ASP solvers are based on (extensions of) technology from Boolean satisfiability solving. While these solvers have shown to be very successful in many practical applications, their strength is limited by their underlying proof system, resolution. In this paper, we present a new tool LP2PB that translates ASP programs into pseudo-Boolean theories, for which solvers based on the (stronger) cutting plane proof system exist. We evaluate our tool, and the potential of cutting-plane-based solving for ASP on traditional ASP benchmarks as well as benchmarks from pseudo-Boolean solving. Our results are mixed: overall, traditional ASP solvers still outperform our translational approach, but several benchmark families are identified where the balance shifts the other way, thereby suggesting that further investigation into a stronger proof system for ASP is valuable.

Related papers

• Learning More Effective Representations for Dense Retrieval through Deliberate Thinking Before Search [65.53881294642451]
  Deliberate Thinking based Dense Retriever (DEBATER) DEBATER enhances recent dense retrievers by enabling them to learn more effective document representations through a step-by-step thinking process. Experimental results show that DEBATER significantly outperforms existing methods across several retrieval benchmarks.
  arXiv  Detail & Related papers  (2025-02-18T15:56:34Z)
• Answer Set Counting and its Applications [0.8158530638728501]
  We developed an exact ASP counter, sharpASP, which utilizes a compact encoding for propositional formulas. In addition, we proposed an approximate ASP counter, named ApproxASP, a hashing-based counter integrating Gauss-Jordan elimination within the ASP solver, clingo.
  arXiv  Detail & Related papers  (2025-02-13T11:52:55Z)
• BRiTE: Bootstrapping Reinforced Thinking Process to Enhance Language Model Reasoning [78.63421517563056]
  Large Language Models (LLMs) have demonstrated remarkable capabilities in complex reasoning tasks. We present a unified probabilistic framework that formalizes LLM reasoning through a novel graphical model. We introduce the Bootstrapping Reinforced Thinking Process (BRiTE) algorithm, which works in two steps.
  arXiv  Detail & Related papers  (2025-01-31T02:39:07Z)
• AxBench: Steering LLMs? Even Simple Baselines Outperform Sparse Autoencoders [73.37603699731329]
  We introduce AxBench, a large-scale benchmark for steering and concept detection. For steering, we find that prompting outperforms all existing methods, followed by finetuning. For concept detection, representation-based methods such as difference-in-means, perform the best.
  arXiv  Detail & Related papers  (2025-01-28T18:51:24Z)
• Can Long-Context Language Models Subsume Retrieval, RAG, SQL, and More? [54.667202878390526]
  Long-context language models (LCLMs) have the potential to revolutionize our approach to tasks traditionally reliant on external tools like retrieval systems or databases. We introduce LOFT, a benchmark of real-world tasks requiring context up to millions of tokens designed to evaluate LCLMs' performance on in-context retrieval and reasoning. Our findings reveal LCLMs' surprising ability to rival state-of-the-art retrieval and RAG systems, despite never having been explicitly trained for these tasks.
  arXiv  Detail & Related papers  (2024-06-19T00:28:58Z)
• Finite Groundings for ASP with Functions: A Journey through Consistency [21.53198582611571]
  It is known that enhancing ASP with function symbols makes basic reasoning problems highly undecidable. We show reductions that give an intuition for the high level of undecidability. These insights allow for a more fine-grained analysis where we characterize ASP programs as "frugal" and "non-proliferous"
  arXiv  Detail & Related papers  (2024-05-08T11:50:08Z)
• CNL2ASP: converting controlled natural language sentences into ASP [4.747324197963404]
  We propose a novel tool, called CNL2ASP, for translating English sentences expressed in a controlled natural language (CNL) form into ASP.
  arXiv  Detail & Related papers  (2023-11-17T13:10:58Z)
• DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases [81.19499764899359]
  We propose a novel framework DecAF that jointly generates both logical forms and direct answers. DecAF achieves new state-of-the-art accuracy on WebQSP, FreebaseQA, and GrailQA benchmarks.
  arXiv  Detail & Related papers  (2022-09-30T19:51:52Z)
• Tools and Methodologies for Verifying Answer Set Programs [0.0]
  ASP is a powerful declarative programming paradigm commonly used for solving challenging search and optimization problems. As an approach to Knowledge Representation and Reasoning, ASP benefits from its simplicity, conciseness and rigorously defined semantics. My research is concerned with extending the theory and tools supporting the verification of ASP progams.
  arXiv  Detail & Related papers  (2022-08-05T10:50:21Z)
• FOLASP: FO(.) as Input Language for Answer Ser Solvers [0.8946655323517091]
  We present a tool that transforms an FO(.) specification into ASP-Core-2, thereby allowing ASP-Core-2 solvers to be used as solvers for FO(.) as well. We present experimental results to show that the resulting combination of our translation with an off-the-shelf ASP solver is competitive with the IDP system as a way of solving problems formulated in FO(.)
  arXiv  Detail & Related papers  (2021-08-09T13:20:26Z)
• Modelling Multi-Agent Epistemic Planning in ASP [66.76082318001976]
  This paper presents an implementation of a multi-shot Answer Set Programming-based planner that can reason in multi-agent epistemic settings. The paper shows how the planner, exploiting an ad-hoc epistemic state representation and the efficiency of ASP solvers, has competitive performance results on benchmarks collected from the literature.
  arXiv  Detail & Related papers  (2020-08-07T06:35:56Z)

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.