Dynamic Membership for Regular Languages

Voices Powered byElevenlabs logo


Antoine Amarilli, Louis Jachiet, Charles Paperman


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.

Follow Us on



Very interesting presentation, even if it's a bit outside my field (quantum computing). It seems to me that there could be some quantum algorithms (based on discrete Fourier transform and quantum phase estimation) that could solve this class of problem more efficiently than the standard approach. Before investing time into it, I am curious though, what is the motivation for studying this problem in the first place?

Can you explain in a few words for non-experts why this particular substitution update/prefix problem is of importance at all? 

What is the Holy Grail goal of this research? I am just wondering if it's a purely mathematical exercise or there is some practical rationale for studying these questions.


Thanks SregeB for your feedback! The motivation for our work is essentially theoretical: we want to understand what it means to evaluate a regular automaton on a changing word. The ultimate goal would be to classify regular languages according to their precise complexity in this sense -- we achieve it conditionally for the O(1) and O(log n / log log n) languages, the O(log log n) class requires more investigation.

I am not familiar with quantum algorithms so I am not sure what would be the complexity of this problem in the quantum setting and whether a different classification could be achieved there, but this could be interesting to figure out!

Add comment
Recommended SciCasts
Recurrent Memory Transformer