Dynamic Word problems

Abstract

Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x=(x_1, x_2, ..., x_n) in M^n, initially (1, 1, ..., 1) with two kinds of operations, for each i in {1, ..., n}, a in M, an operation change_{i,a} which changes x_i to a and a single operation product returning ½_{i=1}^j x_i. This is the dynamic word problem. If we in addition for each j in {1, ..., n} have an operation prefix_j returning ½_{i=1}^j x_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. f