Computing constrained default extensions – a constraint satisfaction problem

Constrained default logic belongs to the class of default logics which formalize default reasoning. This type of nonmonotonic reasoning is modelled by defaults which permit inferring conclusions in the absence of complete information, using default assumptions. Using the classical inference rules and the defaults, the set of initial facts is extended with formulas, called nonmonotonic theorems (beliefs), obtaining extensions. This paper presents a new approach in computing constrained extensions. We define the problem of computing the generating default sets of extensions as a constraint satisfaction problem and we introduce BTCE algorithm for solving this problem. The proposed algorithm is based on a top-down approach and uses pruning for an efficient search.