TY - GEN

T1 - Computing stable models

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

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

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 -