Abstract

We consider extensions of first-order logic (FO) and fixed-point logic (FP) with operators that compute the rank of a definable matrix over a finite field. These operators can be seen as generalisations of more traditional counting operators: instead of counting the cardinality of a definable set, they count the dimension of a definable vector space.

We show that all known examples of polynomial time queries that are not definable in FP with counting operators are definable in the extension of FP with rank. The rank operators turn out to be surprisingly expressive, even in the absence of fixed-point operators. We show that FO with rank operators over the prime field of characteristic p (FO+rk(p)) can define deterministic and symmetric transitive closure. This allows us to show that, on ordered structures and for all prime values of p, FO+rk(p) captures the complexity class MOD -L, whose descriptive complexity had been previously unknown.

This is joint work with Anuj Dawar as well as Martin Grohe and Bastian Laubner (Berlin Humboldt).