TY - JOUR

T1 - A computable semantics for general logic programs

AU - Wallace, Mark

PY - 1989/5

Y1 - 1989/5

N2 - Semantics for positive programs have been thoroughly explored in the context of Herbrand models through the immediate consequence function T. For general logic programs, i.e. programs whose clauses may contain negative literals in their body, parallel semantics have been developed using three-valued logic and a new immediate consequence function Φ. However, over Herbrand models this semantics is not in general computable. A computable subclass is introduced in this paper, termed the canonical general programs. Our main result is to show, constructively, that thislatter class is in some sense representative of all general logic programs, thus extending to general logic programs a result proven recently by Jaffar and Stuckey for positive logic programs. The new result is obtained by providing a transformation which, given any general logic program GP, produces a canonical general logic program CGP "semantically equivalent" to GP in the sense that it has the same success set and finite failure set. It intuitively means that the declarative semantics of CGP captures exactly the set of answer computable from GP.

AB - Semantics for positive programs have been thoroughly explored in the context of Herbrand models through the immediate consequence function T. For general logic programs, i.e. programs whose clauses may contain negative literals in their body, parallel semantics have been developed using three-valued logic and a new immediate consequence function Φ. However, over Herbrand models this semantics is not in general computable. A computable subclass is introduced in this paper, termed the canonical general programs. Our main result is to show, constructively, that thislatter class is in some sense representative of all general logic programs, thus extending to general logic programs a result proven recently by Jaffar and Stuckey for positive logic programs. The new result is obtained by providing a transformation which, given any general logic program GP, produces a canonical general logic program CGP "semantically equivalent" to GP in the sense that it has the same success set and finite failure set. It intuitively means that the declarative semantics of CGP captures exactly the set of answer computable from GP.

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

U2 - 10.1016/0743-1066(89)90017-4

DO - 10.1016/0743-1066(89)90017-4

M3 - Article

AN - SCOPUS:0024657171

VL - 6

SP - 269

EP - 297

JO - Journal of Logic Programming

JF - Journal of Logic Programming

SN - 0743-1066

IS - 3

ER -