grASP: A Graph Based ASP-Solver and Justification System

• URL: http://arxiv.org/abs/2104.01190v1
• Date: Fri, 2 Apr 2021 18:16:20 GMT
• Title: grASP: A Graph Based ASP-Solver and Justification System
• Authors: Fang Li, Huaduo Wang, Gopal Gupta
• Abstract summary: 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.
• Score: 5.098678276629787
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Answer set programming (ASP) is a popular nonmonotonic-logic based paradigm for knowledge representation and solving combinatorial problems. Computing the answer set of an ASP program is NP-hard in general, and researchers have been investing significant effort to speed it up. The majority of current ASP solvers employ SAT solver-like technology to find these answer sets. As a result, justification for why a literal is in the answer set is hard to produce. There are dependency graph based approaches to find answer sets, but due to the representational limitations of dependency graphs, such approaches are limited. We propose a novel dependency graph-based approach for finding answer sets in which conjunction of goals is explicitly represented as a node which allows arbitrary answer set programs to be uniformly represented. Our representation preserves causal relationships allowing for justification for each literal in the answer set to be elegantly found. Performance results from an implementation are also reported. Our work paves the way for computing answer sets without grounding a program.

Related papers

• Exact ASP Counting with Compact Encodings [32.300155018027624]
  This paper presents a new ASP counting framework, called sharpASP, which counts answer sets avoiding larger input formulas. Our empirical analysis over 1470 benchmarks demonstrates significant performance gain over current state-of-the-art exact answer set counters.
  arXiv  Detail & Related papers  (2023-12-19T08:27:29Z)
• IASCAR: Incremental Answer Set Counting by Anytime Refinement [18.761758874408557]
  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.
  arXiv  Detail & Related papers  (2023-11-13T10:53:48Z)
• Generalizing Level Ranking Constraints for Monotone and Convex Aggregates [0.0]
  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.
  arXiv  Detail & Related papers  (2023-08-30T09:04:39Z)
• 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)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)
• 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)
• 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)
• Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus [19.27379168184259]
  The Abstraction and Reasoning Corpus (ARC) aims at benchmarking the performance of general artificial intelligence algorithms. The ARC's focus on broad generalization and few-shot learning has made it impossible to solve using pure machine learning. We propose Abstract Reasoning with Graph Abstractions (ARGA), a new object-centric framework that first represents images using graphs and then performs a search for a correct program.
  arXiv  Detail & Related papers  (2022-10-18T14:13:43Z)
• 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)
• Graph-Based Tri-Attention Network for Answer Ranking in CQA [56.42018099917321]
  We propose a novel graph-based tri-attention network, namely GTAN, to generate answer ranking scores. Experiments on three real-world CQA datasets demonstrate GTAN significantly outperforms state-of-the-art answer ranking methods.
  arXiv  Detail & Related papers  (2021-03-05T10:40:38Z)
• Brain-inspired Search Engine Assistant based on Knowledge Graph [53.89429854626489]
  DeveloperBot is a brain-inspired search engine assistant named on knowledge graph. It constructs a multi-layer query graph by splitting a complex multi-constraint query into several ordered constraints. It then models the constraint reasoning process as subgraph search process inspired by the spreading activation model of cognitive science.
  arXiv  Detail & Related papers  (2020-12-25T06:36: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.