Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Énumération exacte d’automates acycliques minimaux et bijection avec les fonctions de parking généralisées
du 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