Dynamic Membership for Regular Languages

Amarilli, Antoine; Jachiet, Louis; Paperman, Charles

Type de document :

Communication dans un congrès avec actes

DOI :

10.4230/LIPIcs.ICALP.2021.116

Titre :

Dynamic Membership for Regular Languages

Auteur(s) :

Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Institut Polytechnique de Paris [IP Paris]
Jachiet, Louis [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Institut Polytechnique de Paris [IP Paris]
Paperman, Charles [Auteur]

Linking Dynamic Data [LINKS]
Université de Lille

Éditeur(s) ou directeur(s) scientifique(s) :

Bansal Nikhil
Merelli Emanuela
Worrell James

Titre de la manifestation scientifique :

ICALP 2021 - 48th International Colloquium on Automata, Languages, and Programming

Ville :

Glasgow

Pays :

Royaume-Uni

Date de début de la manifestation scientifique :

2021-07-12

Titre de la revue :

Leibniz International Proceedings in Informatics (LIPIcs)

Éditeur :

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Date de publication :

2021-07-02

Mot(s)-clé(s) en anglais :

regular language
membership
RAM model
updates
dynamic

Discipline(s) HAL :

Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Complexité [cs.CC]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Réponse efficace aux requêtes sous mises à jour

Commentaire :

34 pages. This is the full version with proofs of the ICALP'21 article