Analyse de paramètres de classes de DAGS – PANDAG

Synthèse du projet : Analyse combinatoire des structures de données compactées

Ce projet propose une approche combinatoire innovante pour l'étude de quatre familles de structures de données obtenues par compactage.

1. Circuits booléens

L'étude des fonctions booléennes représentées par des circuits compactés constitue un défi majeur. Contrairement aux formules arborescentes classiques, les circuits permettent le partage de sous-structures, créant des graphes acycliques dirigés complexes. Les questions centrales portent sur la distribution probabiliste des fonctions : probabilité d'obtenir une tautologie, persistance de l'effet Shannon. Les premiers résultats suggèrent un comportement différent des modèles arborescents. Le défi réside dans le développement d'outils combinatoires adaptés aux modèles basés sur le partage.

2. Diagrammes de décision binaire

Ces structures révolutionnent la représentation des fonctions booléennes par compactage d'arbres de décision. Le défi combinatoire principal consiste à établir une fonction génératrice nécessitant la mémorisation du profil complet. Une approche récente utilise l'inclusion-exclusion pour éviter cette complexité. Les objectifs incluent l'échantillonnage uniforme efficace et l'analyse des propriétés cryptographiques des fonctions obtenues.

3. Structures DAG croissantes

Extension des arbres récursifs, ces structures relaxent les contraintes d'étiquetage en autorisant les répétitions de labels. Ce modèle généralise les processus phylogénétiques où plusieurs branches se divisent simultanément. La transformée de Borel approximative résout les équations fonctionnelles complexes. Les défis incluent l'extension par substitution de sous-arbres et l'adaptation aux modèles phylogénétiques non-plans.

4. Extensions exploratoires

Deux directions émergent : compilation de connaissances et algorithmes textuels. Les langages d-DNNF en intelligence artificielle représentent des bases de connaissances avec contraintes de déterminisme. Dans le domaine textuel, les arbres trie compactés révèlent des économies par partage de suffixes. Les structures DAWG présentent des dépendances complexes entre suffixes, constituant des défis combinatoires majeurs.

Impact

Ce projet unifie l'analyse de structures distinctes sous le prisme du compactage. Les outils développés révolutionneront la compréhension théorique avec des retombées en algorithmique, cryptographie, intelligence artificielle et bio-informatique.

Pour le moment une équipe franco-autrichienne de 3 chercheurs, un doctorant et une doctorante travaillent sur la modélisation pour le point 1.

Un premier résultat vient d'être soumis à publication pour le point 2. Il s'agit de l'article (et du code associé) présenté dans ce dépôt : hal.sorbonne-universite.fr/hal-05183438v1.

Les deux chercheurs, associés à un doctorants sont en train d'exploiter ces résultats quantitatifs afin de définir des algorithmes de génération aléatoire et par unranking. Les outils sont finaliser et sont en train d'être rédigés.

Concernant le point 3., un post-doctorant ainsi que deux chercheurs du projet sont en train de travailler dans deux directions diverses : l'une pour revisiter le contexte des arbres binaires construits via des processus de croissance et l'autre pour analyser des DAG par couches issus de sous-structures de plus courts chemins dans des graphes.

Le point 4. est pour le moment entre-aperçus dans les perspectives des résultats en cours de finalisation du point 2.

Toutes nos avancées reposent sur des outils de génération et de simulation que nous proposons au téléchargement accompagnant nos articles scientifiques.

Nous nous sommes rencontrés au mois de mai 2025, afin de confronter nos diverses pistes de recherche et d'unifier nos approches : pandag.proj.lip6.fr/workshop-2025/

Les premiers résultats sont prometteurs, et nous sommes confiants pour pouvoir présenter des avancées majeures pour chacun des 4 points que nous avons soulevés lors de l'écriture du projet.

Plusieurs réunions bilatérales France/Autriche, mais aussi Caen/Paris et Paris/Paris sont prévues au cours de l'automne 2025.

Les graphes dirigés acycliques sont étroitement liés aux ordres partiels, ce qui en fait une structure générale et importante. Des familles de DAGs sont apparues en informatique dès les premières procédures de compression de structures arborescentes. Les premières études ont eu lieu dans les années 70, en particulier pour l'énumération. Nos compétences résident dans l'analyse d'algorithmes en utilisant les méthodes de la combinatoire analytique pour décrire la structure combinatoire, trouver de nouvelles spécifications et exhiber des propriétés universelles. Dans ce projet, nous souhaitons étudier des structures d'arbres et leurs DAGs associés. Nous prévoyons de d'étendre la méthodologie à ces DAGs selon trois directions principales:
(i) analyse de la compression dans les tries;
(ii) structure typique de grands DAGs en lien avec les arbres sous-jacents;
(iii) Enumération, génération aléatoire et satisfaisabilité de différents types de diagrammes de décision et circuits booléens.