First-order logic over classes of graphs with bounded expansion

Prelegent(ci)

Wojciech Kazana

Afiliacja

INRIA and ENS Cachan

Termin

28 czerwca 2012 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Luc Segoufin

Seminarium

Seminarium „Teoria automatów”

---

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.

---