Talks and Poster Presentations (with Proceedings-Entry):
M. Gebser, T. Schaub, H. Tompits, S. Woltran:
"Alternative Characterizations for Program Equivalence under Answer-Set Semantics Based on Unfounded Sets";
Talk: 5th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'08),
- 2008-02-15; in: "Proceedings of the 5th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'08)",
S. Hartmann, G. Kern-Isberner (ed.);
Logic programs under answer-set semantics constitute an important tool for declarative problem solving. In recent years, two research issues received growing attention. On the one hand, concepts like loops and elementary sets have been proposed in order to extend Clark´s completion for computing answer sets of logic programs by means of propositional logic. On the other hand, different concepts of program equivalence, like strong and uniform equivalence, have been studied in the context of program optimization and modular programming. In this paper, we bring these two lines of research together and provide alternative characterizations for different conceptions of equivalence in terms of unfounded sets, along with the related concepts of loops and elementary sets. Our results yield new insights into the model theory of equivalence checking. We further exploit these characterizations to develop novel encodings of program equivalence in terms of standard and quantified propositional logic, respectively.
answer set programming, equivalence, logic programming, loops, elementary sets
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Electronic version of the publication:
Project Head Hans Tompits:
Formale Methoden zur Optimierung Nichtmonotoner Logikprogramme
Created from the Publication Database of the Vienna University of Technology.