Fusion trees can be implemented with AC(0) instructions only

Addressing a problem of Fredman and Willard, we implement fusion trees in d eterministic 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 l inear space under insertion, deletion, predecessor, and successor queries, with O(log n/log log n) amortized time per operation on a RAM with word siz e w, where the only computational instructions allowed on the RAM are funct ions 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.