VAL@SAIL.STANFORD.EDU.UUCP (01/27/87)
Commonsense and Nonmonotonic Reasoning Seminar
A QUERY ANSWERING ALGORITHM
FOR CIRCUMSCRIPTIVE AND CLOSED-WORLD THEORIES
Teodor C. Przymusinski
University of Texas at El Paso
<ft00@utep.bitnet>
Thursday, January 29, 4pm
Bldg. 160, Room 161K
McCarthy's theory of circumscription appears to be the most powerful
among various non-monotonic logics designed to handle incomplete and
negative information in knowledge representation systems. In this
presentation we will describe a query answering algorithm for
circumscriptive theories.
The algorithm is based on a modified version of ordered linear resolution
(OL-resolution), which we call a MInimal model Linear Ordered resolution
(MILO-resolution). MILO-resolution constitutes a sound and complete procedure
to determine the existence of minimal models satisfying a given formula.
Our algorithm is the first query evaluation algorithm for general
circumscriptive theories. The Closed-World Assumption (CWA) and its
generalizations, the Generalized Closed-World Assumption (GCWA) and
the Extended Closed-World Assumption (ECWA), can be considered as
special forms of circumscription. Consequently, our algorithm also
applies to answering queries in theories using the Closed-World Assumption
and its generalizations. Similarly, since prioritized circumscription
is equivalent to a conjunction of (parallel) circumscriptions, the
algorithm can be used to answer queries in theories circumscribed by
prioritized circumscription.