Guarded resolution for answer set programming. (English) Zbl 1223.68104
Summary: We investigate a proof system based on a guarded resolution rule and show its adequacy for the stable semantics of normal logic programs. As a consequence, we show that the Gelfond-Lifschitz operator can be viewed as a proof-theoretic concept. As an application, we find a propositional theory \(E_{P}\) whose models are precisely stable models of programs. We also find a class of propositional theories \(\mathcal C_{P}\) with the following properties. Propositional models of theories in \(\mathcal C_{P}\) are precisely stable models of \(P\), and the theories in \(\mathcal C_{T}\) are of the size linear in the size of \(P\).
MSC:
68T15 | Theorem proving (deduction, resolution, etc.) (MSC2010) |
68N17 | Logic programming |
Keywords:
guarded resolution; proof-theory for answer set programming; positive unit resolution; guarded atoms; guarded Horn clauses; stable semantics of logic programs; Gelfond-Lifschitz operatorSoftware:
ASSATReferences:
[1] | Karp, Languages with Expressions of Infinitary length (1964) · Zbl 0127.00901 |
[2] | Marek, The Logic Programming Paradigm pp 375– (1999) · doi:10.1007/978-3-642-60085-2_17 |
[3] | Gelfond, Proc. of the Fifth International Conference and Symposium on Logic Programming pp 1070– (1988) |
[4] | Lifschitz, 24th International Conference on Logic Programming, ICLP 2008 pp 37– (2008) |
[5] | Lifschitz, Annals of Mathematics and Artificial Intelligence 7 pp 261– (2006) |
[6] | Dung, Proc. of North American Conference on Logic Programming pp 604– (1989) |
[7] | Fages, Journal of Methods of Logic in Computer Science 1 pp 51– (1994) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.