A Three-Valued Characterization for Strong Equivalence of Logic Programs

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Knowledge Representation

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.