Dynamic word problems

Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x=(x₁,x₂ ,...,x_n)∈Mⁿ, initially (1,1,...,1) with two kinds of operations, for each i∈{1,...,n}, a∈M, an operation change_i,a which changes x_i to a and a single operation product returning Π_i=1ⁿx_i . This is the dynamic word problem. If we in addition for each j∈{1,...,n} have an operation prefix_j returning Π_i=1^jx_i, we talk about the dynamic prefix problem. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits. We obtain a classification of the complexity based on algebraic properties of M