Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire du LRI
Arbres enrichis
Daniele Gardy

17 February 2012, 14:30 - 17 February 2012, 15:30
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

Résumé :
Prenons une expression logique du calcul des propositions: elle peut être représentée sous forme arborescente. Suivant les règles de construction de la formule, l'arbre sera binaire ou non, planaire ou non, et étiqueté avec différents connecteurs ou littéraux. L'énumération de tels arbres, et l'étude de leurs propriétés statistiques, sont un domaine classique d'application de la combinatoire analytique. Prenons maintenant une formule du calcul des prédicats: l'existence de quantificateurs fait que nous ne pouvons plus a priori utiliser une représentation arborescente. L'énumération de telles formules ne peut alors plus se faire suivant les techniques classiques d'énumération d'arbres, et requiert de nouvelles approches.

Une formule du calcul des prédicats est un cas particulier de ce que nous nommons "arbre enrichi": c'est un arbre auquel on ajoute des arcs partant de certains noeuds (ici ceux correspondant aux quantificateurs) et allant vers des feuilles. De manière équivalente, cela revient à colorer des arbres selon certaines règles; on peut aussi voir ces structures comme une classe particulière de graphes orientés acycliques.

Je présenterai les résultats (déjà obtenus ou en cours de finalisation) sur certaines familles d'arbres enrichis, relatifs à leur énumération et à certains paramètres, puis les possibilités d'extension à des modèles plus généraux.

Pour en savoir plus :
Séminaires
Programming computing media (reporté)
Combinatorics
Friday 18 September 2020 - 14:30
Salle : 445 - PCRI-N
Frédéric Gruau .............................................

forum-dev Continuous Integration
Friday 05 June 2020 - 10:00
Salle : 0 - 650
Erik Bray .............................................

Large-scale Spectral Clustering for GPU-based Plat
High-performance computing
Tuesday 24 March 2020 - 10:30
Salle : 465 - PCRI-N
Guanlin He .............................................

Recherche Opérationnelle à Google
Stochastic Combinatorial Optimization
Thursday 12 March 2020 - 14:30
Salle : 445 - PCRI-N
Laurent Perron .............................................

Forum dev-LRI
Wednesday 05 February 2020 - 14:00
Salle : 455 - PCRI-N
Erik Bray .............................................