TY - JOUR

T1 - Extremal problems in logic programming and stable model computation

AU - Cholewinski, Pawel

AU - Truszczynski, Miroslaw

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1999/2

Y1 - 1999/2

N2 - We study the following problem: given a class of logic programs script c sign, determine the maximum number of stable models of a program from script c sign. We establish the maximum for the class of all logic programs with at most n clauses, and for the class of all logic programs of size at most n. We also characterize the programs for which the maxima are attained. We obtain similar results for the class of all disjunctive logic programs with at most n clauses, each of length at most m, and for the class of all disjunctive logic programs of size at most n. Our results on logic programs have direct implication for the design of algorithms to compute stable models. Several such algorithms, similar in spirit to the Davis-Putnam procedure, are described in the paper. Our results imply that there is an algorithm that finds all stable models of a program with n clauses after considering the search space of size O(3n/3) in the worst case. Our results also provide some insights into the question of representability of families of sets as families of stable models of logic programs.

AB - We study the following problem: given a class of logic programs script c sign, determine the maximum number of stable models of a program from script c sign. We establish the maximum for the class of all logic programs with at most n clauses, and for the class of all logic programs of size at most n. We also characterize the programs for which the maxima are attained. We obtain similar results for the class of all disjunctive logic programs with at most n clauses, each of length at most m, and for the class of all disjunctive logic programs of size at most n. Our results on logic programs have direct implication for the design of algorithms to compute stable models. Several such algorithms, similar in spirit to the Davis-Putnam procedure, are described in the paper. Our results imply that there is an algorithm that finds all stable models of a program with n clauses after considering the search space of size O(3n/3) in the worst case. Our results also provide some insights into the question of representability of families of sets as families of stable models of logic programs.

KW - Answer sets

KW - Disjunctive programs

KW - Extremal problems

KW - Stable models

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

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

U2 - 10.1016/S0743-1066(98)10020-1

DO - 10.1016/S0743-1066(98)10020-1

M3 - Article

AN - SCOPUS:0033078898

VL - 38

SP - 219

EP - 242

IS - 2

ER -