|
Evènement pour le groupe Séminaire Méthodes Formelles
Date | 2016-03-22 14:15-16:00 |
Titre | For graphs of bounded tree width, recognisability equals definability in MSO. |
Résumé | We prove a conjecture of Bruno Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is recognizable in the sense that constant-width tree decompositions of graphs satisfying the property can be recognized by tree automata. In our proof, we show that for every k there is an mso transduction which computes tree decompositions for graphs of tree-width at most k. One of the ingredients is the Factorisation Forest Theorem of Imre Simon. |
Lieu | 75 |
Orateur | Mikolaj Bojanczyk |
Email | http://www.mimuw.edu.pl/~bojan/ |
Url | University of Warsaw |
Aucun document lié à cet événement. RetourRetour à l'index
| |