Mathematical reasoning, formalized in classical logical systems as the production
of a set of theorems {}from a set of axioms, is of course monotonic with respect to inclusion. Since
what may be deduced is what holds in every model of the axioms, enlarging the set of assumptions
restricts the set of acceptable models and thus increases the set of deducible consequences. In the
real world, however, reasoning may follow a different paradigm. Often it is appropriate to admit
only typical situations which fit some given initial information, without taking every remote
possibility into account. Under this paradigm, reasoning is not generally monotonic. For with the
addition of new information, different cases may qualify as typical, with some characteristics
changed {}from those accepted before. Operationally, applications based on this approach, such as
deductive databases or some aspects of robotics, might incorporate a mechanism for making
revisions. More fundamentally, any system involving this type of reasoning must have some
satisfactory basis beyond classical logic for deriving conclusions.
Since the late 1970's, a number of formalisms for nonmonotonic reasoning have been proposed, based
on different intuitions and formulated in diverse ways. They differ in applicability, and on
examples where they can be compared they may not agree. For various systems, individually and
jointly, researchers have examined syntax and semantics, the complexity of calculations, what
concepts are expressible, and how well the formal answers accord with intuition. Such analysis has
led to improvements and refinements, and, more significantly, to some understanding of general
principles.
In this regard, particular progress has come about through comparing different systems on the basis
of their intended models. Important examples of intended models are the minimal, stable, and
supported models associated with different semantics for logic programming, and, by translation,
with the semantics for various other systems. Though much has been learned about their structure,
no full description of these classes of models has previously been given.
The main contribution of this paper is to characterize among the sets of appropriate interpretations
for the language those which are the minimal, stable, and supported model classes of programs. This
is accomplished by viewing the interpretations as points in a topological space; the subsets of the
space corresponding to classes of a given sort are then found to be distinguished by particular
topological properties. The study involves both the Cantor topology familiar {}from descriptive set
theory and the less well--known inverse--Scott topology, defined originally in domain theory in
connection with representing information about computations. We view the topological approach as a
supplement to and extension of the usual recursion--theoretic analysis, whose use is appropriate in
this situation as a setting for distinguishing the roles of negative and positive information in
determining these classes. Furthermore the properties which characterize these classes are in fact
found to depend on such topological concepts as closure and compactness.
The basic characterization results are stated in Theorem~\ref{thm.min} for minimal model classes,
Theorems~\ref{thm.stab1}, \ref{thm.stab2}, and \ref{thm.stab3} for stable model classes (in
different forms), and Theorem~\ref{thm.supp} for supported model classes. Closely related to the
topological characterizations are results of two other sorts: descriptions of the classes in terms
of formulas extracted {}from the programs, and normal forms for programs representing given classes.
Results of the first sort have previously been given for supported models (\cite{cl78}) and for
stable models (\cite{mnr90b}); we obtain in Theorem~\ref{thm.minelts} a similar description for
minimal models. We make explicit a normal form representation for stable model classes
(Proposition~\ref{prop.canonstab}) due to
\cite{mnr90b}, and provide such forms also for minimal model classes (Theorem~\ref{thm.prereqfree})
and for supported model classes (Corollary~\ref{cor.canonsupp}). We include algorithms for
calculating minimal models {}from programs and vice versa; in other cases the theorems themselves
provide procedures for calculations. As an application of compactness, we obtain characterization
results for the stable and supported model classes of programs with certain finiteness properties
(Theorems~\ref{thm.fps} and \ref{thm.fc}). Finally we describe how the classes of intended models
can be broadened via a natural transformation $h$\/ introduced in \cite{mnr90a,mnr92b} for studying
Turing complexity (Theorems~\ref{thm.hstab}--\ref{thm.hfc}). Examples are included at every stage
to mark distinctions among conditions.
The presentation is as follows: In Chapter~\ref{chap.introduction} we review the introduction of
various forms of nonmonotonic reasoning and the subsequent development of a more comprehensive point
of view. We also discuss the application of topological ideas to logical questions and introduce
the Cantor and inverse--Scott topologies. We conclude the introductory section by setting our main
question in the context of previous results. Chapter~\ref{sec.min} contains the results on minimal
model classes, which are basic to the further development. Chapter~\ref{sec.stab} relates stable
models to minimal models to obtain characterizations for stable model classes, and
Chapter~\ref{sec.fps} treats the special case of stable model classes of finite proof support
programs. Chapters~\ref{sec.supp} and \ref{sec.fc} obtain analogous results for supported model
classes, first of general programs and then of programs with the finite completion property.
Finally Chapter~\ref{sec.h} establishes characterization results involving the transformation $h.$