Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, p. 337-344Article 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, p. 337-344
Keywords [en]
fusion trees, AC0 instructions, models of computation
Identifiers
URN: urn:nbn:se:uu:diva-25786OAI: oai:DiVA.org:uu-25786DiVA, id: diva2:53560
Available from: 2007-02-13 Created: 2007-02-13 Last updated: 2011-01-14

Open Access in DiVA

No full text in DiVA

Authority records

Andersson, Arne

Search in DiVA

By author/editor
Andersson, Arne
By organisation
Computing Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 977 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf