R28  
On Computing Minimal Models
Rachel BenEliyahu(rachelb@cs.technion.ac.il) &
Rina Dechter (dechter@ics.uci.edu)

Abstract This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the first group are efficient when the theory is almost Horn, that is, when there are few nonHorn clauses and/or when the set of all literals that appear positive in any nonHorn clause is small. Algorithms in the other group are efficient when the theory can be represented as an acyclic network of lowarity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of finding minimal models. [ps] [pdf] 