COMPUTING DOWNWARDS ACCUMULATIONS ON TREES QUICKLY

Downwards passes on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certa in conditions, a downwards pass is both 'efficient' (computable in a f unctional style in parallel time proportional to the depth of the tree ) and 'manipulable' (enjoying a number of distributivity properties us eful in program construction); we call a downwards pass satisfying the se conditions a downwards accumulation. In this paper, we show that th ese conditions do in fact yield a stronger conclusion: the accumulatio n can be computed in parallel time proportional to the logarithm of th e depth of the tree, on a CREW PRAM machine.