1. |
- Andersson, Arne, et al.
(författare)
-
Fusion trees can be implemented with AC0 instructions.
- 1999
-
Ingår i: Theoretical Computer Science. ; 205, s. 337-344
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
2. |
- Brodnik, Andrej, et al.
(författare)
-
Trans-dichotomous algorithms without multiplication : some upper and lower bounds
- 1997
-
Ingår i: Algorithms and Data Structures. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 9783540633075 ; , s. 426-439
-
Konferensbidrag (refereegranskat)abstract
- We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear space and with query time log n(log log n)1+0(1). On the way, we show that two w-bit words can be multiplied in time (log w)1+0(1) and that time (log w) is necessary, and that (log log w) time is necessary and sufficient for identifying the least significant set bit of a word.
|
|