Sökning: onr:"swepub:oai:DiVA.org:uu-25786" >
Fusion trees can be...
Fusion trees can be implemented with AC0 instructions.
-
- Andersson, Arne (författare)
- Uppsala universitet,Datalogi
-
Miltersen, Peter Bro (författare)
-
Thorup, Mikkel (författare)
-
(creator_code:org_t)
- 1999
- 1999
- Engelska.
-
Ingår i: Theoretical Computer Science. ; 205, s. 337-344
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- 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.
Nyckelord
- fusion trees
- AC0 instructions
- models of computation
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas