A Three-Valued Characterization for Strong Equivalence of Logic Programs

Pedro Cabalar, University of Corunna

In this work we present additional results related to the property of strong equivalence of logic programs. This property asserts that two programs share the same set of stable models, even under the addition of new rules. As shown in a recent work by Lifschitz, Pearce and Valverde, strong equivalence can be simply reduced to equivalence in the logic of Here-and-There (HT). In this paper we provide an alternative based on 3-valued logic, using also, as a first step, a classical logic charaterization. We show that the 3-valued encoding provides a direct interpretation for nested expressions but, when moving to an unrestricted syntax, it generally yields different results from HT.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.