You are not logged in |
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
- 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.
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.
