A vi Si/berschalztt

This paper is concerned with the issue of parallel evaluation of logic pro-grams. We define the concept of program decomposability, which means that the load of evaluation can be partitioned among a number of processors, without a need for communication among them. This in turn results in a very significant speed-up of the evaluation process. Some programs are decomposable, whereas others are not. We completely syntactically characterize three classes of single rule programs with respect to decomposability: nonrecursive, simple linear, and simple chain programs. We also establish two sufficient conditions for decom-posability