Computing Preferred and Weakly Preferred Answer Sets by Meta-Interpretation in Answer Set Programming

This page describes how to use DLV as a tool for computing preferred and weakly preferred answer sets, as described in the paper "Computing Preferred Answer Sets by Meta-Interpretation in Answer Set Programming" by Thomas Eiter, Wolfgang Faber, Nicola Leone, and Gerald Pfeifer, available as INFSYS RR-1843-01-11, also at CoRR in arXiv.org as cs.LO/0201013.

A preliminary version bearing the same title and authors has been published in the "Proceedings of the AAAI 2001 Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, Stanford, CA, March 2001" by AAAI Press on pages 45-52. It is also available via the web.

This work is based on work done by Gerd Brewka and Thomas Eiter, specifically, Preferred Answer Sets for Extended Logic Programs, Artificial Intelligence, 109(1-2):297--356, 1999 (extended Report).

Another basis of this work is the paper A Comparative Study of Logic Programming with Preference by Torsten Schaub and Kewen Wang, which appeared in the Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'01), pages 597-602, 2001.

Ingredients

To experiment with preferred and weakly preferred answer sets, you will need the following three ingredients:

• A version of DLV supporting weak constraints. The first such version has been released on October 15th, 2000.
• Meta-interpreter programs, you can find them below.
• Prioritzied programs in the format accepted by the meta-interpreters. We also provide some example programs taken from the related papers.

Meta-interpreters

We provide all meta-interpreters presented in INFSYS RR-1843-01-11 plus four bonus interpreters. You can download all of them in a single .tar.gz archive or individually below. The tar file contains the following files:

asi

Answer Set Interpreter
as found in the paper

b-pasi

Basic B-Preferred Answer Set Interpreter
almost as found in the paper; we use in_PAS instead of in_CP

b-pasi.graph

B-Preferred Answer Set Interpreter implementing the graph algorithm
almost as found in the paper; there is an additional rule defining in_PAS at the end

w-pasi

Basic W-Preferred Answer Set Interpreter
as found in the paper

d-pasi

Basic D-Preferred Answer Set Interpreter
as found in the paper

b-wpasi

Weakly B-Preferred Answer Set Interpreter
almost as found in the paper; we use in_WPAS instead of in_CP

b-pasi.alternative

Alternative B-Preferred Answer Set Interpreter
based on the characterisation in (Schaub&Wang, 2001), existence is mentioned in the paper at the end of section 4.2

b-pasi.alternative2

Alternative B-Preferred Answer Set Interpreter
very similar to b-pasi.alternative, but zombie rule detection is done earlier

w-pasi.alternative

Alternative W-Preferred Answer Set Interpreter
Instead of generating and testing arbitrary sets of literals, take only answer sets, using the answer set meta-interpreter
Use it at your own risk

d-pasi.alternative

Alternative D-Preferred Answer Set Interpreter
Instead of generating and testing arbitrary sets of literals, take only answer sets, using the answer set meta-interpreter
Use it at your own risk

Format of the Input Programs

As described in the paper, prioritized programs should be encoded in the following way: A rule labeled r of the form

r: A :- B1,...,Bm, not C1,..., not Cn.

is represented by facts

rule(r). head(A,r).
pbl(B1,r). ... pbl(Bm,r).
nbl(C1,r). ... nbl(Cn,r).

Rule preferences r < r' are specified as facts pr(r,r')., and complementary classical literals l and l' are specified as facts compl(l,l')..

Some Examples

Here we provide a number of examples, including all examples in our paper, and all examples from (Brewka&Eiter, 1999) and (Schaub&Wang, 2001) in the format described above. You can download all of them in a single .tar.gz archive or individually below. The tar file contains the following files:

be-3.1

Example 3.1 from (Brewka&Eiter, 1999)

be-3.2

Example 3.2 from (Brewka&Eiter, 1999)

be-4.1

Example 4.1 from (Brewka&Eiter, 1999)

be-5.3

Example 5.3 from (Brewka&Eiter, 1999)

be-5.4

Example 5.4 from (Brewka&Eiter, 1999)

be-5.5

Example 5.5 from (Brewka&Eiter, 1999), Example 6 in our paper

be-6.3

Example 6.3 from (Brewka&Eiter, 1999), Example 12 in our paper

be-6.3a

A variation of Example 6.3 from (Brewka&Eiter, 1999), given in Example 9 in our paper

be-6.5

Example 6.5 from (Brewka&Eiter, 1999)

be-proof-6.6

Example given in the proof for Proposition 6.6 in (Brewka&Eiter, 1999)

buy-car

Qualitative Decision Making Application given in section 8 of (Brewka&Eiter, 1999)

buy-car1

Variation of buy-car, also given in section 8 of (Brewka&Eiter, 1999)

penguin

The famous bird & penguin example, occurs in Examples 1, 4, 5, 7, 8,10 in our paper, also in (Brewka&Eiter, 1999), Examples 2.1, 4.3

penguin-conclusions

A variation of the famous bird & penguin example, found in the conclusions of (Brewka&Eiter, 1999)

no_prioriy.1

A small program not containing any priorities

sw-pi2

Program Pi2 of (Schaub&Wang, 2001)

sw-pi3

Program Pi3 of (Schaub&Wang, 2001)

sw-pi_prime3

Program Pi'3 of (Schaub&Wang, 2001)

unfounded.1

A small program not containing priorities, but an unfounded set

unfounded.2

Another small program not containing priorities, but an unfounded set

unfounded.3

Yet another program not containing priorities, but an unfounded set

Usage

Assume that you have the file penguin from above and the meta-interpreter for B-preferred answer sets b-pasi from above in the current working directory. Assume further that you have an executable DLV in your path. Then the following command-line will compute and print the single preferred answer set for that example:

DLV b-pasi penguin -filter=in_PAS

The output will look like

{in_PAS(peng), in_PAS(bird), in_PAS(neg_flies)}

-filter is a command-line option of DLV that allows for printing a subset of the predicates of an answer set. In our case there are a lot of auxiliary predicates. If you are curious and want to see them anyway, just remove -filter=in_PAS, or add -filter=interesting_predicate.

Now let us turn to weakly preferred answer sets. Assume that the file be-6.3 and that the meta-interpreter for weakly B-preferred answer sets b-wpasi are both in the current directory and DLV is in your path. Issuing the command

DLV b-wpasi be-6.3 -filter=in_WPAS

yields the following output:

Optimal answer set: {in_WPAS(c), in_WPAS(neg_d)}
Cost ([Weight:Level]): <[1:1]>

In addition to the weakly preferred answer set, you can also see the preference violation degree, which is the weight (the first integer) printed in the second line, 1 in this example. The level (the second integer) will always be one here.

The invocation for example programs with the other meta-interpreters is analogous. The only difference are the names representing answer sets, preferred answer sets, and weakly preferred answer sets, respectively. They are in_AS, in_PAS, and in_WPAS, respectively.

Find below a summary associating these predicate names with the meta-interpreters.

asi

in_AS

b-pasi

in_PAS

b-pasi.graph

in_PAS

w-pasi

in_PAS

d-pasi

in_PAS

b-wpasi

in_WPAS

b-pasi.alternative

in_PAS

b-pasi.alternative2

in_PAS

w-pasi.alternative

in_PAS

d-pasi.alternative

in_PAS