Dynamic membership for regular languages

DOI10.4230/LIPICS.ICALP.2021.116MaRDI QIDQ7241216zbMATH OpenFDO

Authors Antoine Amarilli, Louis Jachiet, Charles Paperman

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.116

zbMATH Keywords

dynamicmembershipRAM modelregular languageupdates

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• Automata theory on sliding windows
• Design and implementation of an efficient priority queue
• Dynamic word problems
• Equivalence between priority queues and sorting
• Finite semigroup varieties of the form V*D
• Finite-automaton aperiodicity is PSPACE-complete
• scientific article; zbMATH DE number 4202347 (Why is no real title available?)
• scientific article; zbMATH DE number 4010784 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 1419248 (Why is no real title available?)
• scientific article; zbMATH DE number 7650239 (Why is no real title available?)
• On dynamic bit-probe complexity
• Querying regular languages over sliding windows
• Regular languages in \(NC\)
• The dynamic complexity of formal languages
• The fundamental lemma of complexity for arbitrary finite semigroups
• The variety generated by finite nilpotent monoids
• Upper and lower bounds for dynamic data structures on strings
• Work-sensitive dynamic complexity of formal languages

Cited in

(2)

• Dynamic direct access of MSO query evaluation over strings
• Dynamic membership for regular tree languages

This page was built for publication: Dynamic membership for regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241216)