Dynamic Complexity of Formal Languages

We will discuss the dynamic complexity of formal languages. As opposed to static complexity theory, which investigates the complexity of problems over fixed structures, dynamic complexity theory concerns the complexity necessary to maintain the answer to a problem on an ever changing structure. In terms of formal languages, this amounts to maintaining whether a changing word is in a given language. We will show that the regular languages are exactly those languages maintainable using quantifier-free first order updates, and consider some related questions.