Dualities between Alternative Semantics for Logic Programming and
Nonmonotonic Reasoning
Chitta R. Baral and V.S. Subrahmanian
Abstract
The Gelfond-Lifschitz operator
\cite{Gelf88} associated with a logic program (and likewise
the operator associated with default theories by Reiter)
exhibits oscillating behavior. In the case of
logic programs, there is always at least
one finite, non-empty collection of Herbrand interpretations around
which the Gelfond-Lifschitz \cite{Gelf88} operator ``bounces around''.
The same phenomenon occurs with default logic when Reiter's operator
$\Gamma _\Delta$ is considered. Based on this, a ``stable class''
semantics and ``extension class'' semantics was proposed in
\cite{BS90a}. The main advantage of this semantics was that
it was defined for all logic programs (and default theories), and
that this definition was modelled using the standard operators
existing in the literature such as Reiter's $\Gamma _\Delta$
operator. In this paper, our primary aim is to prove that
there is a very interesting {\em duality} between stable class
theory and the well founded semantics for logic programming.
In the stable class semantics, classes that were minimal
with respect to Smyth's power-domain ordering were selected.
We show that the well founded semantics precisely corresponds
to a class that is minimal w.r.t. Hoare's power domain
ordering: the well known dual of Smyth's ordering. Besides
this elegant duality, this immediately suggests how to define a
well-founded semantics for default logic in such a
way that the dualities
that hold for logic programming continue to hold for default
theories.
We show how the same technique may be applied to ``strong''
auto-epistemic logic: the logic of strong expansions proposed
by Marek and Truszczynski \cite{Mare89a}.