Logics with Rank Operators

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

• Bjarki Holm (University of Cambridge)
• Monday 23 February 2009, 12:45-14:00
• Room FW26, Computer Laboratory, William Gates Building.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Room FW26, Computer Laboratory, William Gates Building
• School of Technology
• Semantics Lunch (Computer Laboratory)
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.