University of Cambridge > Talks.cam > Semantics Lunch (Computer Laboratory) > Logics with Rank Operators

Logics with Rank Operators

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Sam Staton.

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).

This talk is part of the Semantics Lunch (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity