Introduction à la théorie des structures et son application aux fonctions Booléennes

La notion de structure transparaît dans de nombreux domaines scientifiques comme une approche pragmatique pour capturer le fait que des objets complexes peuvent être décomposés en éléments plus simples. Nous proposons une formalisation de cette notion et montrons comment s’en servir pour unifier diverses variations des diagrammes de décision binaires (BDD, une représentation simple, pragmatique, canonique et raisonnablement efficace pour manipuler les fonctions Booléennes) présents dans la littérature scientifique. En particulier, (1) nous montrons que garantir la canonicité de telles représentations est drastiquement plus simple que précédemment perçu, et (2) nous introduisons la notion de ‘confluence structurelle’ pour formaliser des éléments peu ou pas adressés par les formalismes précédents.

Cette présentation sera agrémentée de résultats expérimentaux pour montrer l’intérêt pratique de notre approche.