LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.

Past Seminars

Logics with Rank Operators

 Anuj Dawar
Tuesday, April 07 2009 at 11:00AM
Salle de Conférence (Pavillon des Jardins)
Anuj Dawar (Computer Laboratory, University of Cambridge, UK)

It is a long-standing open problem in descriptive complexity theory whether there is a logic that expresses exactly the polynomial-time decidable properties of unordered structures. It has been known since the early 90s that fixed-point logic with counting (FPC) is not sufficient and there have been several proposals for more expressive logics. Taking our inspiration from recent results that show that natural linear-algebraic operations are not definable in FPC, we propose FPR - an extension of fixed-point logic with an operator for matrix rank. We show that this is strictly more expressive than FPC and can express the polynomial-time problems that have been shown to be inexpressible in FPC. We also show that FO+R, the extension of first-order logic with rank operators is surprisingle expressive. It can express some forms of transitive closure and, on ordered structures, captures the complexity classes ModpL.

In this talk, I will give the history and general background to the question (assuming little or no previous knowledge of descriptive complexity and fixed-point logics) and explain the context of the new results. I will also point to several interesting open problems.

(Joint work with Martin Grohe, Bjarki Holm and Bastian Laubner).

About LSV