Wissensverarbeitung und Informationssysteme

NoMoRe$^<$
Graphs and colorings for answer set programming with preferences

Susanne Grell

Kathrin Konczak

Torsten Schaub

Universität Potsdam, Institut für Informatik,

email: sgrell@rz.uni-potsdam.de, {konczak, torsten}@cs.uni-potsdam.de

Contents

• Introduction
• Installation
• Getting started
• Operators
• Options
• Download
• Bibliography

Introduction

The integration of preferences into answer set programming constitutes an important practical device for distinguishing certain preferred answer sets from non-preferred ones. To this end, we elaborate upon rule dependency graphs and their colorings for characterizing different preference handling strategies found in the literature. We exemplarily develop an operational characterization for computing preferred answer sets (according to D-preferences [1]) in terms of operators on partial colorings. In analogy to the notion of a derivation in proof theory, our operational characterization is expressed as a (non-deterministically formed) sequence of colorings, gradually turning an uncolored graph into a totally colored one. The NoMoRe$^<$ system is divided in several components which read an ordered logic program out of a file, generate the ordered rule dependence graph (DG ), which represents the ordered logic program, and compute order preserving admissible colorings , which corresponds to preferred answer sets of ordered logic programs.

The implementation is written in C++.

Installation

It is important that you have correctly installed a c++ compiler on your machine. (The system has been successfully tested with gcc version 3.3.2.) Additionally, you also need to have installed lparse version 1.13.

Now you must download and unpack the NoMoRe$^<$ files.

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

After unpacking you find the source files in the /nomorepref/ directory.

To install the NoMoRe$^<$ system run:

> ./configure
> make

Then, the executable file nomorepref is created under /nomorepref-1.0/src/.

To install NoMoRe$^<$ under /usr/local/bin/ you have to run:

> make install

Now the NoMoRe$^<$ system should be install and ready to use.

Getting started

The best way to explain the use of the NoMoRe$^<$ system is to run an exemplary session. The Preferences are encoded in the following format:

• rules are labeled by adding a ''name'' atom to the positive body of the rule

• these ''name'' atoms also have to appear as facts in the logic program

• the preferences itselves are encoded by using the ''preferred'' predicate, where preferred(rule1, rule2) means that the rule labelled with ``rule1'' is preferred over the rule labelled with ``rule2''

Let us consider the following example, called littleexample.lp:

$$\begin{array}{lrclccc} r_1: & a & \leftarrow & name(r1), ... ...& name(r2).&& \\ r_5: & preferred(r1,r2).&&\\ \end{array}$$ (1)

The preference states that rule r1 is higher preferred than rule r2, which results in the only preferred answer set {a}.

To compute the preferred answer sets for our example we proceed in the following way:

1. Start a shell and change into the directory containing the logic program.

2. Next parse the logic program with preferences using lparse and pipe the output into the NoMoRe$^<$ system. We have the following system call:

   lparse -d all littleexample.lp | nomorepref -pref

   The lparse option -d all is essential. It is not possible to correctly compute preferred answer sets, if this option is omitted, since lparse would delete information we need.

3. The output of NoMoRe$^<$ returns additionally to the preferred answer sets, conclusions about the number of choice points and the duration for computing the order preserving admissible colorings.

   nomorepref 0.1 Reading ... done
   Preferred Answer Set 1:
   a 
   No
   Time: 0.000
   Call to choice points    : 1
   

Operators

We have developed different operators for computing deterministic consequences ($P$, $U$) for answer sets with and without preferences, choices $C$ and $D$ for computing answer set without preferences and the choice operators $D$ and $DH$ for computing answer sets with preferences. Furthermore, we have developed different strategies for coloring sequences for computing preferred answer sets. (For more details see ([2])

Options

When using NoMoRe$^<$ different options can be specified.

nomorepref [number] [-pref] [-op pre:nd:d:post]

number	specifies the number of answer sets to be computed, if this option is omitted or set to 0 all answer sets are computed
-pref	only preferred answer sets will be computed
-op	the following string has to be enclosed in " ", it is used to specify the operators used, the default is "Pre:D:(Ps,U)*:N"
pre	specifies the preprocessing operator, possible are Pre or None
nd	specifies the non-deterministic (choice) operator, e.g. D, DH
d	specifies the deterministic operator / a sequence of deterministic operators, e.g. (Ps,U)*
	Ps stands for $\mathcal{P}$*, which represents the Fitting operator
	U stands for $\mathcal{U}$*, to compute the unfounded sets
	(Ps,U)* stands for ($\mathcal{P}$*$\mathcal{U}$)*, which computes the well founded semantics
post	specifies the postprocessing operator, e.g. N or None
	N stands for the $\mathcal{N}$ operator

When using the -op option it is possible to combine different operators, but not all combinations are possible, e.g. it is not possible to use the DH operator if all standard answer sets are computed and not only the preferred ones

The most efficient coloring sequences are:
-op DH:(Ps,U)*:N
-op D:(Ps,U)*:N

Calls for littleexample.lp could look like the following:
lparse -d all littleexample.lp | nomorepref 0 -pref -op ''Pre:DH:(Ps,U)*:N''
lparse -d all littleexample.lp | nomorepref 0 -pref -op ''Pre:D:(Ps,U)*:N''

For more details about coloring sequences see [2].

Download

• Here you can download the current version of the NoMoRe$^<$ system (nomorepref-1.0.tar.gz).

Bibliography

1

J. Delgrande, T. Schaub, H. Tompits, and K. Wang.
Towards a classification of preference handling approaches in nonmonotonic reasoning.
In U. Junker, editor, Proceedings of the Workshop on Preferences in Artificial Intelligence and Constraint Programming: Symbolic Approaches, pages 16-24. AAAI Press, 2002.

2

K. Konczak, T. Schaub, and T. Linke.
Graphs and colorings for answer set programming with preferences.
Fundamenta Informaticae, 57(2-4):393-421, 2003.