Computer Science – Artificial Intelligence
Scientific paper
2000-02-27
Journal of Automated Reasoning 28(1):53-97, 2002
Computer Science
Artificial Intelligence
Slight modification
Scientific paper
Global SLS-resolution and SLG-resolution are two representative mechanisms for top-down evaluation of the well-founded semantics of general logic programs. Global SLS-resolution is linear for query evaluation but suffers from infinite loops and redundant computations. In contrast, SLG-resolution resolves infinite loops and redundant computations by means of tabling, but it is not linear. The principal disadvantage of a non-linear approach is that it cannot be implemented using a simple, efficient stack-based memory structure nor can it be easily extended to handle some strictly sequential operators such as cuts in Prolog. In this paper, we present a linear tabling method, called SLT-resolution, for top-down evaluation of the well-founded semantics. SLT-resolution is a substantial extension of SLDNF-resolution with tabling. Its main features include: (1) It resolves infinite loops and redundant computations while preserving the linearity. (2) It is terminating, and sound and complete w.r.t. the well-founded semantics for programs with the bounded-term-size property with non-floundering queries. Its time complexity is comparable with SLG-resolution and polynomial for function-free logic programs. (3) Because of its linearity for query evaluation, SLT-resolution bridges the gap between the well-founded semantics and standard Prolog implementation techniques. It can be implemented by an extension to any existing Prolog abstract machines such as WAM or ATOAM.
Shen Yi-Dong
You Jia-Huai
Yuan Li-Yan
No associations
LandOfFree
SLT-Resolution for the Well-Founded Semantics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with SLT-Resolution for the Well-Founded Semantics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and SLT-Resolution for the Well-Founded Semantics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-144997