TY - GEN

T1 - Strong equivalence for logic programs and default theories (Made Easy)

AU - Turner, Hudson

PY - 2001

Y1 - 2001

N2 - Logic programs P and Q are strongly equivalent if, given any logic program R, programs P ∩ R and Q ∩ 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. Recently, Lifschitz, Pearce and Valverde showedthat Heyting's logic of here-and-there can be used to characterize strong equivalence of logic programs. This paper offers a more direct characterization, and extends it to default logic. In their paper, Lifschitz, Pearce and Valverde study a very general form of logic programs, called" nested" programs. For the study of strong equivalence of default theories, it is convenient to introduce a corresponding "nested" version of default logic, which generalizes Reiter's default logic.

AB - Logic programs P and Q are strongly equivalent if, given any logic program R, programs P ∩ R and Q ∩ 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. Recently, Lifschitz, Pearce and Valverde showedthat Heyting's logic of here-and-there can be used to characterize strong equivalence of logic programs. This paper offers a more direct characterization, and extends it to default logic. In their paper, Lifschitz, Pearce and Valverde study a very general form of logic programs, called" nested" programs. For the study of strong equivalence of default theories, it is convenient to introduce a corresponding "nested" version of default logic, which generalizes Reiter's default logic.

UR - http://www.scopus.com/inward/record.url?scp=84864208682&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864208682&partnerID=8YFLogxK

U2 - 10.1007/3-540-45402-0_6

DO - 10.1007/3-540-45402-0_6

M3 - Conference contribution

AN - SCOPUS:84864208682

SN - 3540425934

SN - 9783540425939

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 92

BT - Logic Programming and Nonmonotonic Reasoning - 6th International Conference, LPNMR 2001, Proceedings

T2 - 6th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2001

Y2 - 17 September 2001 through 19 September 2001

ER -