• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Dynamic Membership for Regular Languages
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Communication dans un congrès avec actes
DOI :
10.4230/LIPIcs.ICALP.2021.116
Title :
Dynamic Membership for Regular Languages
Author(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Jachiet, Louis [Auteur]
Data, Intelligence and Graphs [DIG]
Paperman, Charles [Auteur] refId
Linking Dynamic Data [LINKS]
Scientific editor(s) :
Bansal Nikhil
Merelli Emanuela
Worrell James
Conference title :
ICALP 2021 - 48th International Colloquium on Automata, Languages, and Programming
City :
Glasgow
Country :
Royaume-Uni
Start date of the conference :
2021-07-12
Journal title :
Leibniz International Proceedings in Informatics (LIPIcs)
Publisher :
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date :
2021-07-02
English keyword(s) :
regular language
membership
RAM model
updates
dynamic
HAL domain(s) :
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Complexité [cs.CC]
English abstract : [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 ...
Show more >
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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
ANR Project :
Réponse efficace aux requêtes sous mises à jour
Comment :
34 pages. This is the full version with proofs of the ICALP'21 article
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • http://arxiv.org/pdf/2102.07728
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017