DYNAMIC WORD-PROBLEMS

Let M be a fixed finite monoid. We consider the problem of implementin g a data type containing a vector x = (x(1), x(2),..., x(n)) is an ele ment of M-n, initially (1, 1,..., 1), with two kinds of operations, fo r each i is an element of (1,..., n) and a is an element of M, an oper ation change(i,a), which changes x(i) to a and a single operation prod uct returning IIi=1n x(i). This is the dynamic word problem for M. If we in addition for each j is an element of (1,..., n) have an operatio n prefix, returning IIi=1j x(i), we get the dynamic prefix problem for M. We analyze the complexity of these problems in the cell probe or d ecision assignment tree model for two natural cell sizes, 1 bit and lo g n bits. We obtain a partial classification of the complexity based o n algebraic properties of M.