Computing stable models: Worst-case performance estimates

Zbigniew Lonc, Miroslaw Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations


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.

Original languageEnglish
Title of host publicationLogic Programming - 18th International Conference, ICLP 2002, Proceedings
EditorsPeter J. Stuckey
Number of pages16
StatePublished - 2002
Event18th International Conference on Logic Programming, ICLP 2002 - Copenhagen, Denmark
Duration: Jul 29 2002Aug 1 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2401 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Logic Programming, ICLP 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Computing stable models: Worst-case performance estimates'. Together they form a unique fingerprint.

Cite this