Wissensverarbeitung und Informationssysteme

`GCasp`
Graphs and colorings for answer set programming

Kathrin Konczak and Thomas Linke and Torsten Schaub

Universität Potsdam, Institut für Informatik

Introduction

We investigate rule dependency graphs and their colorings for characterizing the computation of answer sets of logic programs [2,3]. To this end, we develop a series of operational characterizations in terms of operators on partial colorings. Our characterizations are expressed as (non-deterministically formed) sequences of colorings, turning an uncolored graph into a totally colored one. This results in an operational framework in which different combinations of operators result in different formal properties.

The GCasp system is divided in several components which read a logic program out of a file, generate the rule dependence graph (RDG), which represents the logic program, and compute the admissible colorings , which corresponds to the answer sets of the logic program. The implementation is written for different Prolog systems like ECLiPSe, SICStus and SWI. Additionally, the well-founded semantics [4] for normal logic programs can be computed.

Architecture

The GCasp system consists of several components for computing answer sets shown in Figure 1.

**Figure 1:** components of the `GCasp` system
$\begin{figure} \begin{picture}(480, 180)(0, 0) \par \put(102, 80){\framebox (3... ...0,-1){40}} \put(370, 100){\vector(0,-1){40}} \end{picture} \end{figure}$

After parsing the normal logic program out of a file the rule dependence graph is constructed. For a better representation the RDG is compiled into temporary files. Now a sequence of operators [2,3] computes admissible colorings of the RDG which correspond to the answer sets of the logic program.

Installation

It is important that you have correctly installed ECLiPSe, SICStus or SWI on your machine. Now you must download and unpack the GCasp files.

> gunzip gcasp-1.0.tar.gz
> tar -xf gcasp-1.0.tar

After unpacking you find the source files in the /GCasp/Source directory. The directory /GCasp/Examples contains some example files. If you want to use a tool for visualization of the RDG, you have to install the daVinci system.

Getting started

The best way to explain the use of the GCasp system is to consult an exemplary session under ECLiPSe prolog.

We want to compute the answer sets of the following logic program [3], stored in Examples/example.lp:

$\begin{displaymath} \begin{array}{lrcl} r_1: & p & \leftarrow & \\ r_2: & b... ..._6: & x & \leftarrow & f,nf,\ensuremath{not}\; x \end{array} \end{displaymath}$

(1)

Change to the directory Source/ and start ECLiPSe.
```
[eclipse 1]:
```

Load the GCasp system by typing [gcasp] and choosing your prolog system.

[eclipse 1]: [gcasp].

   .....

!!!!! Which Prolog are you working with?
!!!!! (enter number followed by ENTER)
!!!!! (0) ECLIPSe  (1) SWI  (2) Sicstus  (3) Exit
!!!!!  0
Flag prolog(eclipse) set
Flag output set
**************************************
ECLiPSe version of the GCasp system
**************************************

  .....

For getting an overview of the flags type flags.

[eclipse 2]: flags.
output = on
prolog(eclipse) = on
prolog(swi) = off
prolog(sicstus) = off
daVinci = off

For creating a daVinci file you must activate the daVinci flag.
```
[eclipse 6]: set_flag(daVinci).
Flag daVinci set
```
Before computing the answer set of the program we must load the desired characterization, for example operational characterization II by typing cload(c2). (For other characterizations, see Figure 2.)
```
[eclipse 3]: cload(c2).
```
Now we can call gcasp('../Examples/example.lp', 0). where the first parameter is the name of the normal logic program and the second value the number of answer sets to search (0 stands for all answer sets).
```
[eclipse 4]: gcasp('../Examples/example.lp', 0).
```
This call returns conclusion about the number of answer sets and choice points and the duration for computation.
```
Answer Set 1: { b, f, p }
Answer Set 2: { b, nf, p }

 ....

number of choice points    : 1
number of solutions        : 2  (for program ../Examples/example.lp)
duration                   : 0.01s
```
Furthermore, the file example.lp.daVinci is created, which is a visualization of the RDG.

For computing the well-founded model of a normal logic program call wfm(+Filename).

[eclipse 5]: wfm('../Examples/example.lp').
computing well-founded model ... ready

Positive part : [b, p]
Negative part : [m]
duration      : 0.0s    (for program ../Examples/examples.lp)

Operators

We have developed different operators for computing deterministic consequences ( $\cal{P}$ , $\cal{U}$ , $\cal{V}$ ) and choices ( $\cal{C}$ , $\cal{D}$ ). For more details see [2,3].

Characterizations

For computing admissible colorings, which corresponds to answer sets, we provide different operational characterizations [2,3].

**Figure 2:** operational characterizations
$\begin{figure}\par \begin{tabular}{\vert c\vert l\vert c\vert}\hline \begin{ta... ...r} & \texttt{cload(c6m).} \ \hline \par \end{tabular}\par \par \end{figure}$

Files

Here you can download the current version of the GCasp system containing the following list of files and directories (gcasp-1.0.tar.gz).
Download daVinci visualization tool for visualization of rule dependency graphs.

Bibliography

1: C. Anger, K. Konczak, and T. Linke.
NoMoRe: Non-monotonic reasoning with logic programs.
In S. Flesca, S. Greco, N. Leone, and G.Ianni, editors, Proceedings of the Eighth European Conference on Logics in Artificial Intelligence (JELIA'02), volume 2424 of Lecture Notes in Artificial Intelligence, pages 521-524. Springer-Verlag, 2002.
2: K. Konczak, T. Linke, and T. Schaub.
Graphs and colorings for answer set programming: Abridged report.
In M. De Voss and A. Provetti, editors, Proceedings of the Second International Workshop on Answer Set Programming (ASP03), volume 78, pages 137-150, Messina, 2003. CEUR Workshop Proceedings.
3: K. Konczak, T. Linke, and T. Schaub.
Graphs and colorings for answer set programming: Abridged report.
In V. Lifschitz and I. Niemelä, editors, Proceedings of the Seventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'04), volume 2923 of Lecture Notes in Computer Science, pages 127 - 140. Springer-Verlag Heidelberg, 2003.
4: A. van Gelder, K. Ross, and J. S. Schlipf.
The well-founded semantics for general logic programs.
Journal of the ACM, 38(3):620-650, 1991.

GCasp Graphs and colorings for answer set programming

Introduction

`GCasp`
Graphs and colorings for answer set programming