A Partial MaxSAT Approach to Nonmonotonic Reasoning with System W

Abstract

The only recently introduced System W is a nonmonotonic
inductive inference operator exhibiting some notable proper-
ties like extending rational closure and satisfying syntax split-
ting postulates for inference from conditional belief bases.
A semantic model of system W is given by its underlying
preferred structure of worlds, a strict partial order on the set
of propositional interpretations, also called possible worlds,
over the signature of the belief base. Existing implementa-
tions of system W are severely limited by the number of
propositional variables that occur in a belief base because
of the exponentially growing number of possible worlds. In
this paper, we present an approach to realizing nonmono-
tonic reasoning with system W by using partial maximum
satisfiability (PMaxSAT) problems and exploiting the power
of current PMaxSAT solvers. An evaluation of our approach
demonstrates that it outperforms previous implementations of
system W and scales reasoning with system W up to a new
dimension.