Graph Based Answer Set Programming Solver Systems

Date

2022-05-01T05:00:00.000Z

Authors

ORCID

Journal Title

Journal ISSN

Volume Title

Publisher

item.page.doi

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. This thesis proposes 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. We explore multiple approaches for executing answer set programs based on this graph representation. These approaches can be broadly classified as bottom-up or top-down. The bottom-up approach finds models by assigning truth values following a topological order, while the top-down approach generates models starting from the constraints imposed by the answer set program. We also demonstrate other applications of our graph representation-based implementation, namely, to answer set program execution visualization, finding defeaters for answer set program queries, implementing alternative semantics of normal logic programs, and finding the set of relevant consistent concepts in the development of automated socialbots.

Description

Keywords

Computer Science

item.page.sponsorship

Rights

Citation