TY - GEN
T1 - Computing stable models
T2 - 18th International Conference on Logic Programming, ICLP 2002
AU - Lonc, Zbigniew
AU - Truszczyński, Miroslaw
PY - 2002
Y1 - 2002
N2 - We study algorithms for computing stable models of propositional logic programs and derive estimates on their worst-case performance that are asymptotically better than the trivial bound of O(m2n), where m is the size of an input program and n is the number of its atoms. For instance, for programs, whose clauses consist of at most two literals (counting the head) we design an algorithm to compute stable models that works in time O(m × 1.44225n). We present similar results for several broader classes of programs, as well.
AB - We study algorithms for computing stable models of propositional logic programs and derive estimates on their worst-case performance that are asymptotically better than the trivial bound of O(m2n), where m is the size of an input program and n is the number of its atoms. For instance, for programs, whose clauses consist of at most two literals (counting the head) we design an algorithm to compute stable models that works in time O(m × 1.44225n). We present similar results for several broader classes of programs, as well.
UR - https://www.scopus.com/pages/publications/84888217420
UR - https://www.scopus.com/pages/publications/84888217420#tab=citedBy
U2 - 10.1007/3-540-45619-8_24
DO - 10.1007/3-540-45619-8_24
M3 - Conference contribution
AN - SCOPUS:84888217420
SN - 3540439307
SN - 9783540439301
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 347
EP - 362
BT - Logic Programming - 18th International Conference, ICLP 2002, Proceedings
A2 - Stuckey, Peter J.
Y2 - 29 July 2002 through 1 August 2002
ER -