Complete problems for dynamic complexity classes

Dynamic complexity classes such as DynFO, described by Immerman and Patnaik, have problems which are complete under bounded expansion reductions. These are reductions in which a change of a single bit in the original structure changes a bounded number of bits in the resulting struc-ture. Once the paper is written rewrite the abstract with much more detailed statement of its content??? 1 Dynamic problems Needs a better introduction and explanation!??? We define a dynamic problem, ffflfiffififlfi , to be a family of regular languages. For each value of is a regular language over !, a polynomial-size alphabet of operations. If string "$#% is in &, we say that the sequence of operations " is accepted by the dynamic problem 1. Work partially supported by NSF grant CCR-9877078. 1To avoid complications in our definition of reductions between problems, we require as part of the definition that the empty string is rejected by all languages () in all dynamic problems. 1 An example of a dynamic problem is the dynamic graph reachability problem DynREACH. This is the dynamic problem induced by the static decision problem REACH. An instance of REACH is a directed graph on nodes, numbered * through , with two distinguished nodes- and.. This instance is accepted if there is a directed path from node- to node.. The dynamic problem DynREACH contains, for each, a regular language DynREACH defined over the set of operation