| Computing Downwards Accumulations on Trees Quickly (1999) | |||||||||||||||
Abstract | |||||||||||||||
| . Downwards accumulations on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certain conditions, a downwards accumulation 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). 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. 1 Introduction The value of programming calculi for the development of correct programs is now clear to the computer science community; their value is even greater for parallel programming than it is for sequential programming, on account of the greater complexity of parallel computations. One such programming calculus is the BirdMeertens formalism (Meertens, 1986; Bird, 1987, 1988;... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||