  Logic programs P and Q are strongly equivalent if, given any program R,
programs P union R and Q union R are equivalent (that is, have the same answer
sets). Strong equivalence is convenient for the study of equivalent
transformations of logic programs: one can prove that a local change is correct
without considering the whole program. Lifschitz, Pearce and Valverde showed
that Heyting's logic of here-and-there can be used to characterize strong
equivalence for logic programs with nested expressions (which subsume the
better-known extended disjunctive programs). This note considers a simpler,
more direct characterization of strong equivalence for such programs, and shows
that it can also be applied without modification to the weight constraint
programs of Niemela and Simons. Thus, this characterization of strong
equivalence is convenient for the study of equivalent transformations of logic
programs written in the input languages of answer set programming systems dlv
and smodels. The note concludes with a brief discussion of results that can be
used to automate reasoning about strong equivalence, including a novel encoding
that reduces the problem of deciding the strong equivalence of a pair of weight
constraint programs to that of deciding the inconsistency of a weight
constraint program.
