Dynamic Complexity under Definable Changes
  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.
