uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Fusion trees can be implemented with AC0 instructions.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
1999 (English)In: Theoretical Computer Science, Vol. 205, 337-344 p.Article in journal (Refereed) Published
Abstract [en]

Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC^o instructions only. More precisely, we show that a subset of {0,...,2^(w-1)} of size n can be maintained using linear space under insertion, deletion, predecessor, and successor queries, with O(log n/loglog n) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are fuinctions in AC^0. The AC^0 instructions used are not all available on today's computers.

Place, publisher, year, edition, pages
1999. Vol. 205, 337-344 p.
Keyword [en]
fusion trees, AC0 instructions, models of computation
URN: urn:nbn:se:uu:diva-25786OAI: oai:DiVA.org:uu-25786DiVA: diva2:53560
Available from: 2007-02-13 Created: 2007-02-13 Last updated: 2011-01-14

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Andersson, Arne
By organisation
Computing Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 187 hits
ReferencesLink to record
Permanent link

Direct link