TY - JOUR

T1 - Computing minimal models, stable models, and answer sets

AU - Lonc, Zbigniew

AU - Truszczyński, Mirosław

PY - 2003

Y1 - 2003

N2 - 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(m1.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.

AB - 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(m1.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.

UR - http://www.scopus.com/inward/record.url?scp=0348155921&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0348155921&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24599-5_15

DO - 10.1007/978-3-540-24599-5_15

M3 - Article

AN - SCOPUS:0348155921

SN - 0302-9743

VL - 2916

SP - 209

EP - 223

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -