Average Time Analyses Related to Logic Programming.
Nachum Dershowitz, Naomi Lindenstrauss · 1989
Logic programs are known to be amenable to parallelization. Our work is an attempt to quantify the magnitude of speed-up one can expect from parallel execution of a logic program. To make average case analysis tractable we look separately at two aspects of logic program execution: the "subgoaling" aspect, which involves trying to prove a goal by using matching to reduce it to other goals and finally to true, and the "goal reduction" aspect, involving full unification. In the first case we assume that the and-or tree determined by a goal can be constructed by matching only, and show---using the generating function approach of Flajolet--- that the average cost of evaluating such trees in parallel tends to a constant as the size tends to infinity, but that the same is true, though with a larger constant, for "clever" sequential evaluation. For the second aspect we use the generating function methods to obtain partial results about unification, which suggest that, although unification may...