Computing Downwards Accumulations on Trees Quickly
<em>Downwards accumulations</em> 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 `manipulabl...
| Egile nagusia: | |
|---|---|
| Formatua: | Conference item |
| Argitaratua: |
Brisbane
1993
|
| _version_ | 1826261034847961088 |
|---|---|
| author | Gibbons, J |
| author_facet | Gibbons, J |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | <em>Downwards accumulations</em> 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. |
| first_indexed | 2024-03-06T19:15:12Z |
| format | Conference item |
| id | oxford-uuid:181b5edf-792b-4cc1-a9ea-85611adc8ae9 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:15:12Z |
| publishDate | 1993 |
| publisher | Brisbane |
| record_format | dspace |
| spelling | oxford-uuid:181b5edf-792b-4cc1-a9ea-85611adc8ae92022-03-26T10:41:24ZComputing Downwards Accumulations on Trees QuicklyConference itemhttp://purl.org/coar/resource_type/c_5794uuid:181b5edf-792b-4cc1-a9ea-85611adc8ae9Department of Computer ScienceBrisbane1993Gibbons, J<em>Downwards accumulations</em> 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. |
| spellingShingle | Gibbons, J Computing Downwards Accumulations on Trees Quickly |
| title | Computing Downwards Accumulations on Trees Quickly |
| title_full | Computing Downwards Accumulations on Trees Quickly |
| title_fullStr | Computing Downwards Accumulations on Trees Quickly |
| title_full_unstemmed | Computing Downwards Accumulations on Trees Quickly |
| title_short | Computing Downwards Accumulations on Trees Quickly |
| title_sort | computing downwards accumulations on trees quickly |
| work_keys_str_mv | AT gibbonsj computingdownwardsaccumulationsontreesquickly |