Computing Downwards Accumulations on Trees Quickly
Jeremy Gibbons
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.
Details
| Address |
Brisbane |
| Book Title |
16th Australian Computer Science Conference |
| Editor |
Gopal Gupta and George Mohay and Rodney Topor |
| Month |
feb |
| Pages |
685–691 |
| Year |
1993 |
Links
Related pages
|
People |
|
|
Activities |