Testing the Equivalence of Logic Programs under Stable Model Semantics

Reference:

Tomi Janhunen and Emilia Oikarinen. Testing the equivalence of logic programs under stable model semantics. In Sergio Flesca, Sergio Greco, Nicola Leone, and Giovambattista Ianni, editors, Logics in Artificial Intelligence, Proceedings of the 8th European Conference, volume 2424 of Lecture Notes in Artificial Intelligence, pages 493–504, Cosenza, Italy, September 2002. Springer-Verlag.

Abstract:

Solving a problem in the answer set programming approach means constructing a logic program so that the answer sets of the program correspond to the solutions to the problem. Typically, a programmer develops a series of improved formulations for a particular problem. Consequently, the programmer is confronted by another problem, namely ensuring that subsequent formulations are equivalent, i.e., give rise to the same answer sets. To ease answer set programming, we propose a methodology for testing the equivalence of logic programs. The basic idea is to translate the logic programs and under consideration into a single logic program whose answer sets (if such exist) yield counter-examples to the equivalence of and . The translation function presented in the paper has been implemented as a translator program LPEQ that enables the equivalence testing of logic programs using the SMODELS system. Experiments performed with LPEQ and SMODELS suggest that establishing the equivalence of logic programs in this way is in certain cases much faster than explicit cross-checking of answer sets.

Suggested BibTeX entry:

@inproceedings{JO02:jelia,
    address = {Cosenza, Italy},
    author = {Tomi Janhunen and Emilia Oikarinen},
    booktitle = {Logics in Artificial Intelligence, Proceedings of the 8th European Conference},
    editor = {Sergio Flesca and Sergio Greco and Nicola Leone and Giovambattista Ianni},
    month = {September},
    pages = {493--504},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Artificial Intelligence},
    title = {Testing the Equivalence of Logic Programs under Stable Model Semantics},
    volume = {2424},
    year = {2002},
}