A representative model based algorithm for maximal contractions

Abstract

In this paper, we propose a representative model based algorithm to calculate maximal contractions. For a formal theory Γ and a fact set Δ, the algorithm begins by accepting all models of refutation by facts of Γ with respect to Δ and filters these models to obtain the models of R-refutation. According to the completeness of R-calculus, the relevant maximal contraction is obtained simultaneously. In order to improve the efficiency, we divide the models into different classes according to the assignments of atomic propositions and only select relevant representative models to verify the satisfiability of each proposition. The algorithm is correct, and all maximal contractions of a given problem can be calculated by it. Users could make a selection according to their requirements. A benchmark algorithm is also provided. Experiments show that the algorithm has a good performance on normal revision problems. © 2012 Science China Press and Springer-Verlag Berlin Heidelberg.