Computer Science – Logic in Computer Science
Scientific paper
2003-12-15
Theory and Practice of Logic Programming, vol 3 (4&5), pages 609-622, 2003
Computer Science
Logic in Computer Science
Scientific paper
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.
No associations
LandOfFree
Strong Equivalence Made Easy: Nested Expressions and Weight Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Strong Equivalence Made Easy: Nested Expressions and Weight Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong Equivalence Made Easy: Nested Expressions and Weight Constraints will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-511014