Computing stable models: worst-case performance estimates

Simple item page
dc.creatorLonc, Zbigniew
dc.creatorTruszczynski, Miroslaw
dc.date2002-05-11
dc.date.accessioned2026-07-07T03:18:23Z
dc.date.available2026-07-07T03:18:23Z
dc.descriptionWe 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(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, as well.
dc.descriptionPaper published in the Proceedings of the International Conference on Logic Programming, ICLP-2002
dc.identifierhttps://arxiv.org/abs/cs/0205013
dc.identifierhttp://arxiv.org/abs/cs/0205013
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31092
dc.subjectLogic in Computer Science
dc.subjectArtificial Intelligence
dc.subjectD.1.6;I.2.4
dc.titleComputing stable models: worst-case performance estimates
dc.typetext

Files

Collections

arXiv