Technical Report CS0516

Title: Logic Programs and a New Approach to Parallelism
Authors: Ouri Wolfson
Abstract: We propose a method of parallelizing bottom-up-evaluation of logic programs. The method is distinguished by the fact that it is pure i.e., does not require interprocessor communication, or synchronization overhead The method cannot be used to parallelize every logic program, but we syntactically characterize several classes pf logic programs to which the method can be applied (e.g., the class of linear single rule programs). We also provide a characterization for a class of prograrns to which the parallelization method cannot be applied, and show that in general, determining applicability is undecidable. Then, we generalize the concepts beyond the proposed method, and lay the foundations for a theory of logic programs and parallelization. It demonstrates that the logic programs have an interesting hierarchical classstructure, with respect to pure parallelization.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1988
To the main CS technical reports page

Computer science department, Technion