Computing Downwards Accumulations on Trees Quickly (1995)

Show simple item record

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


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics