joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, Wied Pakusa

Speaker(s)

Eryk Kopczyński

Affiliation

Uniwersytet Warszawski

Date

March 14, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

Logics with algebraic operators

Seminar

Seminar Automata Theory

---

The quest for a logic for PTIME is one of the central open problems in both finite model theory and database theory. Specifically, it asks whether there is a logic in which a class of finite structures is expressible if, and only if, membership in the class is decidable in deterministic polynomial time. After extending the first order logic with fix point operators (which correspond to recursion) and counting, there are still some problems which can be solved in polynomial time, but are not expressible in our logic. It turns out that most of these problems reduce to some kind of algebraic questions. Is the given system of linear equations solvable? What is the rank of the given matrix? Thus, the natural next step is to try to extend our logic with quantifiers which answer such questions.

In the talk I will give a general introduction to logics which capture parts of PTIME, and some of the current results regarding such logics with algebraic operators.

---