Dynamic Word Problems

Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x=(x/sub 1/, x/sub 2/, .. ., x/sub n/)/spl isin/M/sup n/, initially (1, 1, .. ., 1) with two kinds of operations, for each i/spl isin/{1, .. ., n}, a/spl isin/M, an operation change/sub i, a/ which changes x/sub i/ to a and a single operation product returning /spl Pi//sub i=1//sup n/x/sub i/. This is the dynamic word problem. If we in addition for each j/spl isin/{1, .. ., n} have an operation prefix/sub j/ returning /spl Pi//sub i=1//sup j/x/sub 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. >

Authors

• Gudmund Skovbjerg Frandsen
• Peter Bro Miltersen
• Sven Skyum

Keywords

• Probes
• Random access memory
• Computer science
• Contracts
• Costs
• Dynamic Problem
• Word Problems
• Cell Size
• Complex Problems
• Kinds Of Operations
• Change I
• Data Structure
• Lower Bound
• Upper Bound
• Sunflower
• Sequence Elements
• Identification Of Elements
• Random Access
• Complex Language
• Local Memory
• Semigroup
• Worst-case Complexity
• Regular Language
• Proof Let
• Parallel Case