Abstraction for ASP Programs

Overview

The available prototype tools are for applying abstraction over a given ASP program on the syntactic level and constructing an abstract ASP program which is an over-approximation, where each original answer set can be mapped to some abstract answer set of the abstract program.
  1. Omission Abstraction and Refinement
    2. [SE18] Zeynep G. Saribatur and Thomas Eiter
    Omission-based Abstraction for Answer Set Programs
    In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2018.[link][pdf]
  2. Domain Abstraction
    3. [SSE19] Zeynep G. Saribatur, Peter Schüller and Thomas Eiter
    Abstraction for Non-Ground Answer Set Programs
    In Proceedings of the 16th European Conference on Logics in Artificial Intelligence (JELIA), 2019.[link][pdf]
  3. Multi-Dimensional Domain Abstraction
    4. [ESS19] Thomas Eiter, Zeynep G. Saribatur and Peter Schüller
    Abstraction for Zooming-In to Unsolvability Reasons of Grid-Cell Problems
    In Proceedings of the IJCAI 2019 Workshop on Explainable Artificial Intelligence (XAI@IJCAI), 2019.[pdf]

Journal Articles

Applications in Abstract Argumentation

ASPARO - Omission Abstraction and Refinement for ASP Programs

Abstract

ASPARO is for applying omission-based abstraction on ground ASP programs. The program constructs an abstract ASP program by omitting the given set of atoms from the program. The basic idea is to (i) project the rules to the non-omitted atoms, and (ii) introduce choice when an atom is omitted from a rule body.

In order to deal with spurious abstract answer sets, a refinement is performed over the abstraction by determining some omitted atoms to be badly omitted and adding them back to the vocabulary. The refinement is performed until a concrete abstract answer set is found.

Download

ASPARO is developed in Python 2.7 and it is available as a source code, asparo.zip. Make sure that the PATH variable of your command shell contains the location of Clingo.

Requirements:

Description

The toolbox contains two scripts, grounding_to_groundatoms.sh which takes as input a ground program and converts it to the supported input format, and program_abs_refine.py (a.k.a. ASPARO) which takes as input the program and the initial omission abstraction.

Example

Consider the following program (ex.lp) and an initial omission abstraction of {b,e}.
c :- not d.
d :- not c.
a :- not b,c.
b :- d,e.
e :- not a.
After converting the program to the input format using the grounding_to_groundatoms.sh script (by calling "./grounding_to_groundatoms.sh ex.lp" to obtain the file ex.lp_groundatoms_rulename), we call ASPARO with
python program_abs_refine.py ex.lp_groundatoms_rulename b,e
The script creates the initial abstract program
c :- not d.
d :- not c.
{a} :- c.
and gets an answer set {c} which is spurious. When checking the answer set, it determines b to be badomit and refines the abstraction by adding it back in the program.
In the new abstract program with omitting only {e}, upon encountering a concrete abstract answer set {c,a}, the script stops.

Benchmarks

The benchmarks reported in [SE18] were conducted with additional scripts to compute the minimal blocker sets of programs, which can be requested.

The collection of all encodings and problem instances for the new benchmarks reported in [SE19] is available here.

DASPAR - Domain Abstraction for ASP Programs

Abstract

DASPAR is for applying domain abstraction on non-ground ASP programs. The program constructs an abstract ASP program given a mapping over the domain elements. The focus is on lifting the built-in relations to the abstract domain. The basic idea is to (i) abstract each atom in the rule, (ii) in case of uncertainty due to the abstraction, guess the rule head, (iii) treat negated literals by shifting their polarity depending on the abstract cluster.

An integration of domain abstraction with a refinement strategy is also implemented, where a local search over possible refinements of an abstraction is conducted.

Download

DASPAR is developed in Python 2.7 and it is available as a source code, daspar.zip. Make sure that the PATH variable of your command shell contains the location of Clingo.

Requirements:

Description

The toolbox contains the script program_dom_abstraction.py (a.k.a. DASPAR) which takes as input an ASP program, the abstraction mapping, the predicate name that the abstraction is applied on, and constructs an abstract program.

Additionally, there is a script mapping_search.py that uses a local search over possible refinements of an abstraction mapping.

Example

Consider the following program and a domain mapping {1,2,3} -> a0 , {4,5} -> a1.
c(X) :- not d(X), dom(X).
d(X) :- not c(X), dom(X).
b(X,Y) :- a(X),d(Y), dom(X), dom(Y).
e(X) :- c(X), a(Y), X≤Y, dom(X), dom(Y).
a(1).a(3).
dom(1..5).
The script program_dom_abstraction.py creates the abstract program
c(X) :- dom(X), not d(X).
{c(X)} :- dom(X).
d(X) :- dom(X), not c(X).
{d(X)} :- dom(X).
b(X,Y) :- a(X), d(Y), dom(X), dom(Y).
%leq,a0,a0,III
{e(X)} :- c(X), a(Y), X≤Y, dom(X), dom(Y), X=a0, Y=a0.
%leq,a1,a1,III
{e(X)} :- c(X), a(Y), X≤Y, dom(X), dom(Y), X=a1, Y=a1.
%leq,a0,a1,I
e(X) :- c(X), a(Y), X≤Y, dom(X), dom(Y), X=a0, Y=a1.

mDASPAR - Multi-dimensional Domain Abstraction for ASP Programs

Abstract

Extension of DASPAR to handle multi-dimensional domain abstract mappings, by abstracting the relations instead of lifting them. Given two predicate names to abstract over, it creates an abstract program with a new abstract object.

An integration with a refinement method to get hints from debugging the spurious abstract answer sets is implemented.

Download

mDASPAR is developed in Python 2.7 and it is available as a source code, mdaspar_v0.2.zip. Make sure that the PATH variable of your command shell contains the location of Clingo.

Requirements:

Old versions: mdaspar_v0.1.zip

Description

The toolbox contains the script program_dom_abstraction_abstract_relations.py (a.k.a. mDASPAR) which takes as input an ASP program, the abstraction mapping, the predicate names (works with 2 sorts) that the abstraction is applied on, and constructs an abstract program.

The script abs_refine_pairs.py is the implementation of the abstraction and refinement methodology.

Feedback

Last update: 2022-06-01 by Zeynep G. Saribatur