Logical Foundations of Well-Founded Semantics

Pedro Cabalar, Sergei Odintsov, David Pearce

We propose a solution to a long-standing problem in the foundations of well-founded semantics (WFS) for logic programs. The problem addressed is this: which (non-modal) logic can be considered adequate for well-founded semantics in the sense that its minimal models (appropriately defined) coincide with the partial stable models of a logic program? We approach this problem by identifying the HT² frames previously proposed by Cabalar to capture WFS as structures of a kind used by Došen to characterise a family of logics weaker than intuitionistic and minimal logic. We define a notion of minimal, total HT² model which we call partial equilibrium model. Since for normal logic programs these models coincide with partial stable models, we propose the resulting partial equilibrium logic as a logical foundation for well-founded semantics. In addition we axiomatise the logic of HT²-models and prove that it captures the strong equivalence of theories in partial equilibrium logic.

Subjects: 3.3 Nonmonotonic Reasoning; 9.3 Mathematical Foundations

Submitted: Mar 6, 2006

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.