Sound and Efficient Non-monotonic Inference

Abstract

We analyze conditions that allow for sound and efficient non-monotonic inference. For that we consider theories comprised of rules and observations and a semantic framework developed elsewhere that allows us to view such theories as dynamic systems: systems with a transition function f that maps states to sets of possible successor states, and a plausibility function 1r that determines the relative likelihood of those transitions . In this framework the transition function f is determined by the rules and the plausibility function 1r is provided independently. In this work we aim to identify plausibility functions that have good semantical and computational properties. We do so by identifying a set of core predictions to be accounted for that can be computed in polynomial time , can be justified in simple terms , and are not tied to either Horn theories or closed world assumptions. The resulting functions allow us to handle an interesting class of theories in a justifiable and efficient manner.