Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T10:45:27.510Z Has data issue: false hasContentIssue false

Computing stable models: worst-case performance estimates

Published online by Cambridge University Press:  06 January 2004

ZBIGNIEW LONC
Affiliation:
Faculty of Mathematics and Information Science, Warsaw University of Technology, 00-661 Warsaw, Poland (e-mail: [email protected])
MIROSŁAW TRUSZCZYŃSKI
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, KY 40506-0046, USA (e-mail: [email protected])

Abstract

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(m 2^n)$, 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\times 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.

Type
Regular Papers
Copyright
© 2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)