2026-07-22T04:11:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14185 2024-03-06T10:53:41Z ddc:004 open_access

Dynamic Membership for Regular Languages Amarilli, Antoine Jachiet, Louis Paperman, Charles regular language membership RAM model updates dynamic 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 Ω(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₁ = {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 [Skovbjerg Frandsen et al., 1997] on the dynamic word problem, and additionally cover regular languages. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Amarilli and Louis Jachiet and Charles Paperman 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.116 urn:nbn:de:0030-drops-141850 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.116 eng https://creativecommons.org/licenses/by/4.0/legalcode