ON KERNELS, DEFAULTS AND EVEN GRAPHS

Extensions in prerequisite-free, disjunction-free default theories hav e been shown to be in direct correspondence with kernels of directed g raphs; hence default theories without odd cycles always have a ''stand ard'' kind of an extension. We show that, although all ''standard'' ex tensions can be enumerated explicitly, several other problems remain i ntractable for such theories: Telling-whether a non-standard extension exists, enumerating all extensions, and finding the minimal standard extension. We also present a new graph-theoretic algorithm, based on v ertex feedback sets, for enumerating all extensions of a general prere quisite-free, disjunction-free default theory (possibly with odd cycle s). The algorithm empirically performs well for quite large theories.