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

Date 2019-09-24  14:00-15:00
TitreArbres infinis réguliers et revêtements universels de graphes finis 
RésuméThe notion of graph covering, from which we get that of a universal covering (an infinite tree) is important in the theory of distributed computing. This aspect will be first reviewed by Yves Métivier. Universal coverings of finite graphs are regular infinite trees, but not all of them. They can be characterized as the strongly regular trees, i.e. those trees that yield finitely regular rooted trees up to isomorphism when taking any vertex as a root. A few words will be said about a beautiful and difficult theorem by Leighton. These facts will be presented by B. Courcelle (and also at BWG 2019). 
OrateurBruno Courcelle et Yves Métivier 

Aucun document lié à cet événement.

Retour à l'index