TY - JOUR
T1 - Computing stable models
T2 - Worst-case performance estimates
AU - Lonc, Zbigniew
AU - Truszczyński, Mirosław
PY - 2004
Y1 - 2004
N2 - We study algorithms for computing stable models of 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.44225 n). We present similar results for several broader classes of programs. Finally, we study the applicability of the techniques developed in the paper to the analysis of the performance of smodels.
AB - We study algorithms for computing stable models of 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.44225 n). We present similar results for several broader classes of programs. Finally, we study the applicability of the techniques developed in the paper to the analysis of the performance of smodels.
KW - Computing stable models
KW - Logic programs
KW - Stable models
KW - Worst-case bounds
UR - https://www.scopus.com/pages/publications/2142811030
UR - https://www.scopus.com/pages/publications/2142811030#tab=citedBy
U2 - 10.1017/s147106840300173x
DO - 10.1017/s147106840300173x
M3 - Article
AN - SCOPUS:2142811030
SN - 1471-0684
VL - 4
SP - 193
EP - 231
JO - Theory and Practice of Logic Programming
JF - Theory and Practice of Logic Programming
IS - 1-2
ER -