joint work with Luc Segoufin

Speaker(s)

Wojciech Kazana

Affiliation

INRIA and ENS Cachan

Date

June 28, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

First-order logic over classes of graphs with bounded expansion

Seminar

Seminar Automata Theory

---

In 2010 it has been shown by Dvorak, Kral and Thomas that the model-checking problem for first-order logic over classes of graphs with bounded expansion can be solved in linear time. In this talk I would like to present a different approach to proving this result.
I will define what does it mean for a class of relational structures (or graphs) to have bounded expansion and show some examples. Then I'll try to advocate that the equivalent notion of transitive-fraternal augmentations can be useful in showing main result. I will also mention its two natural extensions and sketch why augmentations might find their use in proving them.

The talk is based on a (still in progress) joint work with Luc Segoufin.

---