Eliminating negation from normal logic programs

Kanchana Kanchanasut, Peter Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAlgebraic and Logic Programming - 2nd International Conference, Proceedings
EditorsHelene Kirchner, Wolfgang Wechler
Number of pages15
ISBN (Print)9783540531623
Publication statusPublished - 1 Jan 1990
Externally publishedYes
Event2nd International Conference on Algebraic and Logic Programming, 1990 - Nancy, France
Duration: 1 Oct 19903 Oct 1990

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume463 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference2nd International Conference on Algebraic and Logic Programming, 1990

Cite this