We study the dynamic membership problem for regular languages: fix a language L, read a word w, build in time O(|w|) a data structure indicating if w is in L, and maintain this structure efficiently under letter substitutions on w. We consider this problem on the unit cost RAM model with logarithmic word length, where the problem always has a solution in O(log |w| / log log |w|) per operation. We show that the problem is in O(log log |w|) for languages in an algebraically-defined, decidable class QSG, and that it is in O(1) for another such class QLZG. We show that languages not in QSG admit a reduction from the prefix problem for a cyclic group, so that they require {\Omega}(log |w| / log log |w|) operations in the worst case; and that QSG languages not in QLZG admit a reduction from the prefix problem for the multiplicative monoid U 1 = {0, 1}, which we conjecture cannot be maintained in O(1). This yields a conditional trichotomy. We also investigate intermediate cases between O(1) and O(log log |w|). Our results are shown via the dynamic word problem for monoids and semigroups, for which we also give a classification. We thus solve open problems of the paper of Skovbjerg Frandsen, Miltersen, and Skyum [30] on the dynamic word problem, and additionally cover regular languages.
翻译：我们研究常规语言的动态会籍问题: 修正语言 L, 读一个字 w, 以时间表示 O( ⁇ w ⁇ ) 构建一个数据结构, 显示是否在L( ⁇ w ⁇ ), 并在字母替换下有效维持这个结构 。 我们用对数字长度来考虑单位成本 RAM 模型中的这一问题, 问题总是在每次操作的 O( log ⁇ w ⁇ / log log ⁇ ⁇ w ⁇ ) 中找到一个解决方案。 我们显示, 问题在于O( log ⁇ w ⁇ / log log ⁇ ⁇ ⁇ ) 中, 问题在于一个在代数定义定义、 可分解的 Q( log log log log ) 中, 问题在于 Q( log log log log) 中, 问题在于多版本的 U1 = Q( Q) QLZG) 中, 问题在于前缀 问题, 问题在于 = Q(1) = Q( r) 1 r r) r r) r) r) 。 因此, 问题也无法 。
相关内容
微信扫码咨询专知VIP会员