Title: Dynamic Complexity under Definable Changes,
Abstract: This paper studies dynamic complexity under definable change operations in
the DynFO framework by Patnaik and Immerman. It is shown that for changes
definable by parameter-free first-order formulas, all (uniform) $AC^1$ queries
can be maintained by first-order dynamic programs. Furthermore, many
maintenance results for single-tuple changes are extended to more powerful
change operations: (1) The reachability query for undirected graphs is
first-order maintainable under single tuple changes and first-order defined
insertions, likewise the reachability query for directed acyclic graphs under
quantifier-free insertions. (2) Context-free languages are first-order
maintainable under $\Sigma_1$-defined changes. These results are complemented
by several inexpressibility results, for example, that the reachability query
cannot be maintained by quantifier-free programs under definable,
quantifier-free deletions.