  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.
