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(m2~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 x 1.44225~n). We present similar results for several broader classes of programs, as well.
展开▼
机译：我们研究用于计算命题逻辑程序的稳定模型的算法，并得出其最坏情况性能的估计，这些估计在渐近性上优于O（m2〜n）的平凡边界，其中m是输入程序的大小，n是数字它的原子。例如，对于程序，其子句最多由两个文字组成（计算头部），我们设计了一种算法来计算在O（m x 1.44225〜n）时间内起作用的稳定模型。对于几类更广泛的程序，我们也给出了类似的结果。
展开▼
