Conference item icon

Conference item

Computing Downwards Accumulations on Trees Quickly

Abstract:
Downwards accumulations on binary trees are essentially functions which pass information down a tree. Under certain conditions, these accumulations are both `efficient' (computable in a functional style in parallel time proportional to the depth of the tree) and `manipulable'. 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.

Actions


Authors


More by this author
Institution:
University of Oxford
Department:
Mathematical, Physical and Life Sciences Division - Department of Computer Science
Role:
Author
Publisher:
Brisbane
Publication date:
1993-02-01
URN:
uuid:181b5edf-792b-4cc1-a9ea-85611adc8ae9
Local pid:
cs:2340

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP