2003 | OriginalPaper | Buchkapitel
Computing Minimal Models, Stable Models, and Answer Sets
verfasst von : Zbigniew Lonc, Mirosław Truszczyński
Erschienen in: Logic Programming
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose and study algorithms for computing minimal models, stable models and answer sets of 2- and 3-CNF theories, and normal and disjunctive 2- and 3-programs. We are especially interested in algorithms with non-trivial worst-case performance bounds. We show that one can find all minimal models of 2-CNF theories and all answer sets of disjunctive 2-programs in time O(m 1.4422..n) (n is the number of atoms in an input theory or program and m is its size). Our main results concern computing stable models of normal 3-programs, minimal models of 3-CNF theories and answer sets of disjunctive 3-programs. We design algorithms that run in time O(m1.6701..n), in the case of the first problem, and in time O(mn22.2720..n), in the case of the latter two. All these bounds improve by exponential factors the best algorithms known previously. We also obtain closely related upper bounds on the number of minimal models, stable models and answer sets a 2- or 3-theory or program may have.