Enhancing Global SLS-Resolution with Loop Cutting and Tabling Mechanisms
Preprint
Abstract
Global SLS-resolution is a well-known procedural semantics for top-down computation of queries under the well-founded model. It inherits from SLDNF-resolution the {\em linearity} property of derivations, which makes it easy and efficient to implement using a simple stack-based memory structure. However, like SLDNF-resolution it suffers from the problem of infinite loops and redundant computations. To resolve this problem, in this paper we develop a new procedural semantics, called {\em SLTNF-resolution}, by enhancing Global SLS-resolution with loop cutting and tabling mechanisms. SLTNF-resolution is sound and complete w.r.t. the well-founded semantics for logic programs with the bounded-term-size property, and is superior to existing linear tabling procedural semantics such as SLT-resolution.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- On the equivalence of the static and disjunctive well-founded semantics and its computationTheoretical Computer Science, 2001
- Implementation of a Linear Tabling Mechanism1999
- An Extension of Van Gelder's Alternating Fixpoint to Magic ProgramsJournal of Computer and System Sciences, 1996
- Efficient top-down computation of queries under the well-founded semanticsThe Journal of Logic Programming, 1995
- Bottom-up evaluation and query optimization of well-founded modelsTheoretical Computer Science, 1995
- Termination of logic programs: the never-ending storyThe Journal of Logic Programming, 1994
- A procedural semantics for well-founded negation in logic programsThe Journal of Logic Programming, 1992
- An analysis of loop checking mechanisms for logic programsTheoretical Computer Science, 1991
- Negation as Failure Using Tight Derivations for General Logic Programs1988
- Negation as Failure1978