of the predicates mentioned in the formula indefinitely, until a fixed point is reached. In implementations, it may be necessary to bound the number of iterations to limit the computation time. The resulting operators are also of interest from a theoretical point of view since they can also be used to characterise complexity classes. We will define first-order with iteration, ; here is a (class of) functions from integers to integers, and for different classes of functions we will obtain different complexity classes . In this section we will write to mean and to mean . We first need to define quantifier blocks (QB), a quantifier block is a list where the s are quantifier-free FO-formulae and s are either or . If is a quantifiers block then we will call the iteration operator, which is defined as written time. One should pay attention that here there are quantifiers in the list, but only variables and each of those variable are used times. We can now define to be the FO-formulae with an iteration operator whose exponent is in the class , and we obtain the following equalities: is equal to FO-uniform ACi, and in fact is FO-uniform AC of depth . is equal to NC. is equal to PTIME. It is also another way to write FO(IFP). is equal to PSPACE. It is also another way to write FO(PFP). Notes References Descriptive complexity Database theory Predicate logic