کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431419 688535 2015 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A framework for computing finite SLD trees
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A framework for computing finite SLD trees
چکیده انگلیسی


• We present a framework for constructing finite representations of logic programming computations.
• We ensure that the computed answers are always preserved and, under some conditions, also the call patterns.
• Our technique can be used as a basis for defining correct program analysis and transformations.

The search space of SLD resolution, usually represented by means of a so-called SLD tree, is often infinite. However, there are many applications that must deal with possibly infinite SLD trees, like partial evaluation or some static analyses. In this context, being able to construct a finite representation of an infinite SLD tree becomes useful.In this work, we introduce a framework to construct a finite data structure representing the (possibly infinite) SLD derivations for a goal. This data structure, called closed SLD tree, is built using four basic operations: unfolding, flattening, splitting, and subsumption. We prove some basic properties for closed SLD trees, namely that both computed answers and calls are preserved. We present a couple of simple strategies for constructing closed SLD trees with different levels of abstraction, together with some examples of its application. Finally, we illustrate the viability of our approach by introducing a test case generator based on exploring closed SLD trees.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Logical and Algebraic Methods in Programming - Volume 84, Issue 2, March 2015, Pages 197–217
نویسندگان
, ,