Relevance in the Computation of Non-monotonic Inferences

Inductive inference operators generate non-monotonic inference relations on the basis of a set of conditionals. Examples include rational closure, system P and lexicographic inference. For most of these systems, inference has a high worst-case computational complexity. Recently, the notion of syntax splitting has been formulated, which allows restricting attention to subsets of conditionals relevant for a given query. In this paper, we define algorithms for inductive inference that take advantage of syntax splitting in order to obtain more efficient decision procedures. In particular, we show that relevance allows to use the modularity of knowledge base is a parameter that leads to tractable cases of inference for inductive inference operators such as lexicographic inference.