Abstract:
Accumulations are higher-order operations on structured objects: they leave the shape of an object unchanged, but replace elements of that object with accumulated information about other elements. Upwards and downwards accumulations on trees are two such operations; they form the basis of many tree algorithms. We present two Erew Pram algorithms for computing accumulations on trees taking O(log n ) time on O (n/log n) processors, which is optional.