IASCAR: Incremental Answer Set Counting by Anytime Refinement

• URL: http://arxiv.org/abs/2311.07233v1
• Date: Mon, 13 Nov 2023 10:53:48 GMT
• Title: IASCAR: Incremental Answer Set Counting by Anytime Refinement
• Authors: Johannes K. Fichte, Sarah Alice Gaggl, Markus Hecher, Dominik Rusovac
• Abstract summary: This paper introduces a technique to iteratively count answer sets under assumptions on knowledge compilations of CNFs that encode supported models. In a preliminary empirical analysis, we demonstrate promising results.
• Score: 18.761758874408557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have many answer sets that cannot be enumerated in practice, but counting still allows quantifying solution spaces. If one counts under assumptions on literals, one obtains a tool to comprehend parts of the solution space, so-called answer set navigation. However, navigating through parts of the solution space requires counting many times, which is expensive in theory. Knowledge compilation compiles instances into representations on which counting works in polynomial time. However, these techniques exist only for CNF formulas, and compiling ASP programs into CNF formulas can introduce an exponential overhead. This paper introduces a technique to iteratively count answer sets under assumptions on knowledge compilations of CNFs that encode supported models. Our anytime technique uses the inclusion-exclusion principle to improve bounds by over- and undercounting systematically. In a preliminary empirical analysis, we demonstrate promising results. After compiling the input (offline phase), our approach quickly (re)counts.

Related papers

• Recursive Visual Programming [53.76415744371285]
  We propose Recursive Visual Programming (RVP), which simplifies generated routines, provides more efficient problem solving, and can manage more complex data structures. We show RVP's efficacy through extensive experiments on benchmarks including VSR, COVR, GQA, and NextQA.
  arXiv  Detail & Related papers  (2023-12-04T17:27:24Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Answering Ambiguous Questions via Iterative Prompting [84.3426020642704]
  In open-domain question answering, due to the ambiguity of questions, multiple plausible answers may exist. One approach is to directly predict all valid answers, but this can struggle with balancing relevance and diversity. We present AmbigPrompt to address the imperfections of existing approaches to answering ambiguous questions.
  arXiv  Detail & Related papers  (2023-07-08T04:32:17Z)
• Towards end-to-end ASP computation [8.804696601388706]
  We propose an end-to-end approach for answer set programming (ASP) and linear algebraically compute stable models satisfying given constraints. We implement Lin-Zhao's theorem citeLin04 together with constraints directly in vector spaces as numerical minimization of a cost function constructed from a matricized normal logic program. We empirically test our approach with programming examples including the 3-coloring and Hamiltonian cycle problems.
  arXiv  Detail & Related papers  (2023-06-12T02:00:22Z)
• Top-Down Knowledge Compilation for Counting Modulo Theories [11.086759883832505]
  Propositional model counting can be solved efficiently when the input formula is in deterministic decomposable negation normal form (d-DNNF) Top-down knowledge compilation is a state-of-the-art technique for solving #SAT problems. We advocate for a top-down compiler based on the traces of exhaustive DPLL(T) search.
  arXiv  Detail & Related papers  (2023-06-07T15:46:28Z)
• Evaluating and Improving Tool-Augmented Computation-Intensive Math Reasoning [75.74103236299477]
  Chain-of-thought prompting(CoT) and tool augmentation have been validated as effective practices for improving large language models. We propose a new approach that can deliberate the reasoning steps with tool interfaces, namely textbfDELI. Experimental results on CARP and six other datasets show that the proposed DELI mostly outperforms competitive baselines.
  arXiv  Detail & Related papers  (2023-06-04T17:02:59Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks [108.4568236569645]
  Chain-of-thoughts prompting (CoT) is by far the state-of-art method for these tasks. We propose Program of Thoughts' (PoT), which uses language models to express the reasoning process as a program. PoT can show an average performance gain over CoT by around 12% across all the evaluated datasets.
  arXiv  Detail & Related papers  (2022-11-22T21:06:00Z)
• Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs [22.39203220587435]
  We present a novel system that is capable of efficiently solving the underlying counting problems required to answer such quantitative reasoning problems. Our system exploits the graph-based measure treewidth and works by iteratively finding and refining (graph) abstractions of an ELP program. It turns out that our approach is competitive with existing systems that were introduced recently.
  arXiv  Detail & Related papers  (2021-08-06T09:46:34Z)
• grASP: A Graph Based ASP-Solver and Justification System [5.098678276629787]
  We propose a novel dependency graph-based approach for finding answer sets in which conjunction of goals is explicitly represented as a node. Our representation preserves causal relationships allowing for justification for each literal in the answer set to be elegantly found.
  arXiv  Detail & Related papers  (2021-04-02T18:16:20Z)
• ASP(AC): Answer Set Programming with Algebraic Constraints [20.559497209595822]
  We introduce Answer Set Programming with Algebraic Constraints (ASP(AC)), where rules may contain constraints that compare semiring values to weighted formula evaluations. This work is under consideration for acceptance in Theory and Practice of Logic Programming.
  arXiv  Detail & Related papers  (2020-08-10T10:20:49Z)

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.