Dynamic word problems
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum · Journal of the ACM · 1997
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 ) ʦ M n , initially (1, 1, . . ., 1), with two kinds of operations, for each i ʦ {1, . . ., n} and a ʦ M, an operation change i,a which changes x i to a and a single operation product returning ͟ iϭ1 n x i .This is the dynamic word problem for M. If we in addition for each j ʦ {1, . . ., n} have an operation prefix j returning ͟ iϭ1 j x i , we get the dynamic prefix problem for M. 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 partial classification of the complexity based on algebraic properties of M.