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