Studying strong equivalence is useful for the practice of answer set programming because of the fact that replacing a group of rules within a program by a strongly equivalent group of rules does not change the meaning of the program. But this behavior is not guaranteed when some symbols are used in the program as placeholders. We show how to remedy this issue by generalizing the definition of strong equivalence. The new definition makes this relation dependent on a user guide—a formal expression describing how programs are expected to be used.

PDF

To Appear Proceedings of International Conference on Logic Programming and Nonmonotonic Reasoning (2026).

@article{fan26a, title={Strong Equivalence of Logic Programs Relative to a User Guide}, author={Jorge Fandinno and Zachary Hansen and Yuliya Lierler and Vladimir Lifschitz}, booktitle={Proceedings of International Conference on Logic Programming and Nonmonotonic Reasoning}, month={January}, url="http://www.cs.utexas.edu/users/ai-labpub-view.php?PubID=128179", year={2026} }