Date: Thursday March 18, 2004 @ 1:30pm
Place: ASB 9705

Speaker: Torsten Schaub, Potsdam University

Title:
Graphs and colorings for answer set programming

Abstract:
We investigate rule dependency graphs and their colorings for characterizing the computation of answer sets of logic programs. We start from a characterization of answer sets in terms of totally colored dependency graphs. To a turn, we develop a series of operational characterizations of answer sets in terms of operators on partial colorings.

In analogy to the notion of a derivation in proof theory, our operational 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. Among others, we identify the basic strategy employed by the noMoRe system and justify its algorithmic approach. Also, we distinguish Fitting's and well-founded semantics.

http://www.cs.sfu.ca/~cl