dc.contributor.author |
Gibbons, J |
en |
dc.date.accessioned |
2009-04-16T23:16:12Z |
en |
dc.date.available |
2009-04-16T23:16:12Z |
en |
dc.date.issued |
1995-03 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-002 (1995) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3511 |
en |
dc.description.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. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
Computing Downwards Accumulations on Trees Quickly (1995) |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |