Computing Downwards Accumulations on Trees Quickly (1992)

Gibbons, J.

dc.contributor.author	Gibbons, J.	en
dc.date.accessioned	2009-04-08T04:02:50Z	en
dc.date.available	2009-04-08T04:02:50Z	en
dc.date.issued	1992-11	en
dc.identifier.citation	Computer Science Technical Reports 064 (1992)	en
dc.identifier.issn	1173-3500	en
dc.identifier.uri	http://hdl.handle.net/2292/3465	en
dc.description	Downwards accumulations on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certain conditions, a downwards accumulation 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). 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	Computer Science Technical Reports	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/csTRcgi.pl?serial	en
dc.title	Computing Downwards Accumulations on Trees Quickly (1992)	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