TY - GEN

T1 - Eliminating negation from normal logic programs

AU - Kanchanasut, Kanchana

AU - Stuckey, Peter

PY - 1990/1/1

Y1 - 1990/1/1

N2 - In this paper, we propose a bottom-up partial evaluation of normal programs with a topdown expansion of negated atoms to obtain equivalent logic programs. A program P is transformed to Pω by a bottom-up computation on the positive component of P while the negative counterpart is left untouched. During this process, we collect all substitutions describing a partial answer set to all the positive atoms in the bodies of P. The declarative semantics of P is given by the completion of Pω. The completed predicate definitions in Pω if they do not contain local variables, can be used as a basis for expanding each negated atom in the bodies of Pω. We show that for a class of programs where every negative subgoal can be expanded, the resultant program P’ is a definite logic program with equality and disequality constraints. If the program falls outside this class, the resultant program may be executed using Chan’s SLD—CNF resolution. Our proposed scheme provides a sound and complete query answering system for a class of programs whose positive part has a finite TP ω and whose clauses satisfy the positive grounded property defined herein. With the bottom-up computation, all infinite positive loops are removed. With all the negated atoms expanded or eliminated at partial evaluation time, less work is required during the run-time query answering and problems with floundering are removed.

AB - In this paper, we propose a bottom-up partial evaluation of normal programs with a topdown expansion of negated atoms to obtain equivalent logic programs. A program P is transformed to Pω by a bottom-up computation on the positive component of P while the negative counterpart is left untouched. During this process, we collect all substitutions describing a partial answer set to all the positive atoms in the bodies of P. The declarative semantics of P is given by the completion of Pω. The completed predicate definitions in Pω if they do not contain local variables, can be used as a basis for expanding each negated atom in the bodies of Pω. We show that for a class of programs where every negative subgoal can be expanded, the resultant program P’ is a definite logic program with equality and disequality constraints. If the program falls outside this class, the resultant program may be executed using Chan’s SLD—CNF resolution. Our proposed scheme provides a sound and complete query answering system for a class of programs whose positive part has a finite TP ω and whose clauses satisfy the positive grounded property defined herein. With the bottom-up computation, all infinite positive loops are removed. With all the negated atoms expanded or eliminated at partial evaluation time, less work is required during the run-time query answering and problems with floundering are removed.

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

U2 - 10.1007/3-540-53162-9_41

DO - 10.1007/3-540-53162-9_41

M3 - Conference Paper

AN - SCOPUS:84910872375

SN - 9783540531623

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 217

EP - 231

BT - Algebraic and Logic Programming - 2nd International Conference, Proceedings

A2 - Kirchner, Helene

A2 - Wechler, Wolfgang

PB - Springer

T2 - 2nd International Conference on Algebraic and Logic Programming, 1990

Y2 - 1 October 1990 through 3 October 1990

ER -