Fusion trees can be implemented with AC0 instructions only

Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC(0) 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/log log n) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are functions in AC(0). The AC(0) instructions used are not all available on today's computers. (C) 1999-Elsevier Science B.V. All rights reserved.