Evènement pour le groupe Séminaire Méthodes Formelles


Date 2016-03-22  14:15-16:00
TitreFor 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. 
Lieu75 
OrateurMikolaj Bojanczyk 
Emailhttp://www.mimuw.edu.pl/~bojan/ 
UrlUniversity of Warsaw 



Aucun document lié à cet événement.

Retour
Retour à l'index