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. 
OrateurMikolaj Bojanczyk 
UrlUniversity of Warsaw 

Aucun document lié à cet événement.

Retour à l'index