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 - http://www.scopus.com/inward/record.url?scp=2142811030&partnerID=8YFLogxK

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

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 -