A Novel Equivalence Notion to Compare Answer-Set Programs over Multi-Layered Inputs

Abstract

In the study of logic programming, notions of equivalence play a significant role. This is due to the fact that under common nonmonotonic semantics, like answer-set programming, two programs sharing the same models (answer sets) does not necessarily yield that they are equivalent in all contexts. Whether this context concerns other program modules or just different data, distinguishes strong from uniform equivalence. We introduce a new notion of equivalence for logic programs under the answer-set semantics that allows to precisely compare and simplify programs that receive input from different sources (i.e., over different alphabets); a setting that previous equivalence notions have not considered, but has some interesting use cases, like data integration or belief merging. Our notion further generalizes relativized equivalence, where equivalence is only required over a parameterized context, and has the core concepts of strong and uniform equivalence as corner cases. We provide a model-theoretic characterization in the spirit of SE-models and establish some theoretical properties including a thorough complexity analysis. Furthermore, using our notion, we can pinpoint the known complexity gap between strong and uniform equivalence, giving insight into why the latter is harder than the former.