[Back]

S. Woltran:
"Deciding Strong Equivalence between Logic Programs";
Talk: Seminarvortrag, Universität Potsdam, Institut für Informatik (invited); 2002-12-10.

In the area of answer-set programming (ASP) it is now recognised that two different notions of equivalence are of importance. On the one hand (ordinary) equivalence, which states that two logic programs posses the same answer sets. On the other hand strong equivalence, which holds between two programs iff the two given programs are equivalent under any possible extension.

Recently, testing (ordinary) equivalence between two extended logic programs has been implemented via ASP itself by means of a linear translation. In the talk we present a similar idea for testing strong equivalence between logic programs. From complexity results, we know that testing strong equivalence of two programs can efficiently be reduced to the test of (ordinary) equivalence between extended logic programs, even if the programs under consideration are from a more general class. Hence, we introduce a translation scheme T such that two programs P and Q are strongly equivalent iff T(P) and T(Q) are equivalent in the ordinary sense. We show that the proposed translation T always yields extended logic programs computable in linear time.