On kernels, defaults and even graphs
Date
1997ISSN
1012-2443Source
Annals of Mathematics and Artificial IntelligenceVolume
20Issue
1-4Pages
1-12Google Scholar check
Metadata
Show full item recordAbstract
Extensions in prerequisite-free, disjunction-free default theories have been shown to be in direct correspondence with kernels of directed graphs hence default theories without odd cycles always have a "standard" kind of an extension. We show that, although all "standard" extensions can be enumerated explicitly, several other problems remain intractable 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 vertex feedback sets, for enumerating all extensions of a general prerequisite-free, disjunction-free default theory (possibly with odd cycles). The algorithm empirically performs well for quite large theories.