Dynamic Word problems - Frandsen, Gudmund Skovbjerg; Miltersen, Peter Bro; Skyum, Sven (DAIMI Report Series, 1993)
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