Abstract:
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 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 logarithm of the depth of the tree, on a Crew
Pram machine.