Computing downwards accumulations on trees quickly Export

@article{citeulike:6074662, 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.}, author = {Gibbons, Jeremy}, citeulike-article-id = {6074662}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0304-3975(96)00114-4}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0304-3975(96)00114-4}, day = {30}, doi = {10.1016/S0304-3975(96)00114-4}, issn = {03043975}, journal = {Theoretical Computer Science}, keywords = {accumulations, homomorphism, performance, trees}, month = {November}, number = {1}, pages = {67--80}, posted-at = {2009-11-05 14:57:41}, priority = {2}, title = {Computing downwards accumulations on trees quickly}, url = {http://dx.doi.org/10.1016/S0304-3975(96)00114-4}, volume = {169}, year = {1996} }

TY - JOUR ID - citeulike:6074662 L3 - citeulike-article-id:6074662 N2 - 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. IS - 1 JF - Theoretical Computer Science SN - 03043975 EP - 80 TI - Computing downwards accumulations on trees quickly VL - 169 SP - 67 KW - accumulations KW - homomorphism KW - performance KW - trees AU - Gibbons, Jeremy PY - 1996/11/30/ UR - http://dx.doi.org/10.1016/S0304-3975(96)00114-4 ER -