Nie jesteś zalogowany |
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
- 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.
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.
