uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Fusion trees can be implemented with AC0 instructions.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
1999 (Engelska)Ingår i: Theoretical Computer Science, Vol. 205, s. 337-344Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
1999. Vol. 205, s. 337-344
Nyckelord [en]
fusion trees, AC0 instructions, models of computation
Identifikatorer
URN: urn:nbn:se:uu:diva-25786OAI: oai:DiVA.org:uu-25786DiVA, id: diva2:53560
Tillgänglig från: 2007-02-13 Skapad: 2007-02-13 Senast uppdaterad: 2011-01-14

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Andersson, Arne

Sök vidare i DiVA

Av författaren/redaktören
Andersson, Arne
Av organisationen
Datalogi

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 875 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf