Dynamic Word problems
DOI:
https://doi.org/10.7146/dpb.v22i438.6755Resumé
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 operationchange
_{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
Downloads
Publiceret
1993-05-01
Citation/Eksport
Frandsen, G. S., Miltersen, P. B., & Skyum, S. (1993). Dynamic Word problems. DAIMI Report Series, 22(438). https://doi.org/10.7146/dpb.v22i438.6755
Nummer
Sektion
Articles
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.