Logics with algebraic operators

Prelegent(ci)

Eryk Kopczyński

Afiliacja

Uniwersytet Warszawski

Termin

14 marca 2012 14:15

Pokój

p. 5870

Tytuł w języku angielskim

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

Seminarium

Seminarium „Teoria automatów”

---

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.

---