Symposium on Theoretical Aspects of Computer Science year (city), pp. numbers www.stacs-conf.org THE DYNAMIC COMPLEXITY OF FORMAL LANGUAGES

Abstract. The paper investigates the power of the dynamic complexity classes DynFO, DynQF and DynPROP over string languages. The latter two classes contain problems that can be maintained using quantifier-free first-order updates, with and without making use of functions, respectively. We show that the languages maintainable in DynPROP exactly constitute the regular languages, even when allowing arbitrary precomputation. This enables us to obtain lower bounds for DynPROP and separates DynPROP from DynQF and DynFO. Further, we prove that any context-free language can be maintained in DynFO and a number of specific context-free languages, for example all Dyck-languages, are maintainable in DynQF. We also investigate the dynamic complexity of the regular tree languages. Furthermore we obtain some results concerning arbitrary structures: There exist first-order definable properties which are not maintainable in DynPROP. On the other hand any existential first-order property can be maintained in DynQF when allowing precomputation. 1