Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2015-05-22  10:45-11:45
TitreÉnumération exacte d’automates acycliques minimaux et bijection avec les fonctions de parking généralisées 
RésuméLes fonctions de parking sont intéressantes pour de nombreuses raisons. Elles sont en bijection avec les séquences de Prüfer, les chemins de Dyck décorés, etc. et sont liées à l’inversion de Lagrange, aux polynômes harmoniques diagonaux, etc. En particulier, elles sont en bijection avec les forêts d’arbres enracinés, autrement dit avec les endo-fonctions acycliques. En 2002, Jim Pitman et Richard P. Stanley ont introduit une généralisation des fonctions de parking. Nous verrons qu'une sous-famille de ces fonctions de parking généralisées est en bijection avec l’ensemble des fonctions de transition des automates finis déterministes acycliques. Nous expliciterons une bijection et nous montrerons que cette dernière transporte une information précieuse sur les langages droits des états de l'automate. Nous utiliserons cette information pour extraire et énumérer les automates acycliques non-initiaux pour lesquels tous les langages droits des états sont distincts. Enfin par une technique usuelle de graphes, nous obtiendrons une formule exacte d’énumération des automates acycliques minimaux.  
Lieu076 
OrateurJean-Baptiste Priez 
Emailjean-baptiste.priez@lri.fr 
UrlLaboratoire de Recherche en Informatique, Université Paris-Sud 11 



Aucun document lié à cet événement.

Retour
Retour à l'index