# Computing Downwards Accumulations on Trees Quickly

Jeremy Gibbons

### Abstract

\em Downwards passes\/ on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certain conditions, a downwards pass is both efficient' (computable in a functional style in parallel time proportional to the depth of the tree) and manipulable' (enjoying a number of distributivity properties useful in program construction); we call a downwards pass satisfying these conditions a \em downwards accumulation. In this paper, we show that these conditions do in fact yield a stronger conclusion: the accumulation can be computed in parallel time proportional to the \em logarithm\/ of the depth of the tree, on a CREW PRAM machine.

Journal
Theoretical Computer Science
Note
Earlier version appeared in Proceedings of the 16th Australian Computer Science Conference‚ Brisbane‚ 1993
Number
1
Pages
67–80
Volume
169
Year
1996