Most real-world reasoning, by computer systems or humans, is "non-monotonic." That is, adding new information not only makes new conclusions possible, but also invalidates some conclusions which were previously correctly drawn. The purpose of this research is to determine by theoretical means the limits on effectively computing various forms of non-monotonic inference - in particular McCarthy's circumscription and Reiter's closed world assumption. These forms of non-monotonic inference are also related in this research to other known mathematical systems.inf The significance of this research is that realistic deduction and inference models are needed for practical, real world computer systems. These systems must be capable of drawing inferences rapidly, even for large and complex problems, and theoretical work can show what kinds of models are feasible.
