COMbinatoire énumérative ET Applications: Génération Aléatoire et Exhaustive – COMETA-GAE

La combinatoire énumérative se concentre sur l'énumération, exacte ou approchée, de certaines structures combinatoires, telles que les arbres, les graphes, les permutations ou les mots de langages formels, qui sous-tendent la modélisation discrète dans de nombreux champs de recherche. Les algorithmes de génération aléatoires de leur côté servent à produire de telles structures, au hasard suivant une distribution cible, ou exhaustivement pour lister toutes les possibilités. Des algorithmes de generation aléatoire et exhaustive sont fréquement développés, en informatique pour des tâches de vérification, en physique statistique pour l'expérimentation in-silico, ou en bioinformatique pour du test statistique.

Le projet COMETA-GAE se concentre sur l'énumération constructive, c-à-d les techniques de comptage qui peuvent être relevées en des procédures de génération efficace. Ce domaine est actif et nous sommes convaincus que le moment est idéal pour un projet collectif de portée significative.

Nous prévoyons de traiter en particulier des structures combinatoires avec séries génératrices D-finie ou satifaisant des équations catalytiques, qui attirent dernièrement beaucoup d'intérêt. Un exemple de défi est de tirer parti du résultat récent de Koechlin et al sur l'interprétation de certaines diagonales de séries rationnelles en terme d'automates de Parikh: typiquement se pose la question de comprendre à quel point ces interprétations sont génériques et d'en déduire des algorithmes effectifs. Nous voulons étendre les outils de l'énumération constructive à de nouvelles classes d'universalité de structures, au delà du paradigme devenu standard des générateurs de Boltzmann, notamment en imposant des contraintes et en ajoutant des décorations. Nous étudirons les façons de combiner ces approches constructives avec les progrès récents de la génération aléatoire tels que le résultat de Sportiello d'optimalité de la complexité en bit pour les structures rationnelles ou algébriques.