Grumbach and Tollu study the effect of adding counting primitives to first-order logic, fixpoint logic, and infinitary logic with a finite number of variables. Such counting extensions are an important topic in finite model theory, which investigates the expressive power of various logics on finite structures. This is relevant to theoretical computer science, since these logics can be used as abstractions of database query languages.

The results reported in this paper are mainly concerned with two kinds of restrictions on the counting primitives, namely unnested counters and counters without free variables. First, a hierarchy of expressive power based on the arity of unnested counters is established. Second, for counters without free variables, the authors show that the  0/1 law  holds for first-order logic with equicardinality quantifiers, and that a limit law holds for a fragment of first-order logic with majority quantifiers. This paper does not contain full proofs of these results; the reader interested in details is referred to another paper [1].

This paper is primarily directed to researchers working in finite model theory or database theory (theory of query languages). It is clearly written, however, and its main message will get across to any theoretical computer scientist familiar with the basics of mathematical logic. A useful list of references provides a good overview of the earlier work done on the subject.