Cumulative default logic: Finite characterization, algorithms, and complexity

摘要

Brewka's Cumulative Default Logic (CDL), a new version of Reiter's default logic, puts emphasis on the joint consistency among the justifications of all applied defaults to obtain cumulativity. In this paper, a finite characterization of CDL extensions using sets of generating defaults is given. From this characterization we derive new algorithms for various reasoning tasks in CDL. Moreover, we show that (propositional) cumulative default reasoning has the same complexity as classical default reasoning.