Dynamic Complexity of Regular Languages: Big Changes, Small Work

Whether a changing string is member of a certain regular language can be maintained in the DynFO framework of Patnaik and Immerman: after changing the symbol at one position of the string, a first-order update formula can express - using additionally stored information - whether the resulting string is in the regular language. We extend this and further known results by considering changes of many positions at once. We also investigate to which degree the obtained update formulas imply work-efficient parallel dynamic algorithms.

Authors

• Felix Tschirbs
• Nils Vortmeier
• Thomas Zeume

Keywords

• dynamic descriptive complexity
• regular languages
• batch changes
• work