Dynamic word problems
Dynamic word problems
复制标题
动态应用题
DOI：
10.1109/sfcs.1993.366840
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Sven Skyum
中科院分区：
文献类型：
--
作者：
G. Frandsen;Peter Bro Miltersen;Sven Skyum
设M是固定有限么半群。我们考虑实现包含向量x=(x/sub1/，x/sub2/，...，x/subn/)/spl isin/M/sup n/的数据类型的问题，初始地(1，1，...，1)具有两种操作，对于每个i/spl isin/{1，...，n}，a/spl isin/M，操作改变/subi，a/将x/subi/改变为a，以及返回/spl Pi/subi=1//sup n/x/subi/的单个操作积。这就是动态单词问题。如果我们对每个j/spl isin/{1，...，n}都有一个操作前缀/subj/Returning/spl Pi//subi=1//sup j/x/subi/，则我们讨论动态前缀问题。我们分析了1比特和对数n比特两种自然信元大小的信元探测或决策分配树模型中这些问题的复杂性。根据M<；<；ETX>；>；的代数性质，给出了复杂性的分类。
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.<<ETX>>