TY - JOUR
T1 - Complexity of computing with extended propositional logic programs
AU - Wiktor Marek, V.
AU - Rajasekar, Arcot
AU - Truszczyński, Mirosław
PY - 1995/9
Y1 - 1995/9
N2 - In this paper we introduce the notion of an F-program, where F is a collection of formulas. We then study the complexity of computing with F-programs. F-programs can be regarded as a generalization of standard logic programs. Clauses (or rules) of F-programs are built of formulas from F. In particular, formulas other than atoms are allowed as "building blocks" of F-program rules. Typical examples of F are the set of all atoms (in which case the class of ordinary logic programs is obtained), the set of all literals (in this case, we get the class of logic programs with classical negation [9]), the set of all Horn clauses, the set of all clauses, the set of all clauses with at most two literals, the set of all clauses with at least three literals, etc. The notions of minimal and stable models [16, 1, 7] of a logic program have natural generalizations to the case of F-programs. The resulting notions are called in this paper minimal and stable answer sets. We study the complexity of reasoning involving these notions. In particular, we establish the complexity of determining the existence of a stable answer set, and the complexity of determining the membership of a formula in some (or all) stable answer sets. We study the complexity of the existence of minimal answer sets, and that of determining the membership of a formula in all minimal answer sets. We also list several open problems.
AB - In this paper we introduce the notion of an F-program, where F is a collection of formulas. We then study the complexity of computing with F-programs. F-programs can be regarded as a generalization of standard logic programs. Clauses (or rules) of F-programs are built of formulas from F. In particular, formulas other than atoms are allowed as "building blocks" of F-program rules. Typical examples of F are the set of all atoms (in which case the class of ordinary logic programs is obtained), the set of all literals (in this case, we get the class of logic programs with classical negation [9]), the set of all Horn clauses, the set of all clauses, the set of all clauses with at most two literals, the set of all clauses with at least three literals, etc. The notions of minimal and stable models [16, 1, 7] of a logic program have natural generalizations to the case of F-programs. The resulting notions are called in this paper minimal and stable answer sets. We study the complexity of reasoning involving these notions. In particular, we establish the complexity of determining the existence of a stable answer set, and the complexity of determining the membership of a formula in some (or all) stable answer sets. We study the complexity of the existence of minimal answer sets, and that of determining the membership of a formula in all minimal answer sets. We also list several open problems.
UR - http://www.scopus.com/inward/record.url?scp=21844513199&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=21844513199&partnerID=8YFLogxK
U2 - 10.1007/BF01536401
DO - 10.1007/BF01536401
M3 - Article
AN - SCOPUS:21844513199
SN - 1012-2443
VL - 15
SP - 357
EP - 378
JO - Annals of Mathematics and Artificial Intelligence
JF - Annals of Mathematics and Artificial Intelligence
IS - 3-4
ER -