Création d'une bibliothèque d'antichaine

Auteurs

Arthur Remaud

Type

techreport

Année

2018

Numéro

1803

Résumé

Dans la théorie des ordres, une antichaine est un sous-ensemble d'éléments tous deux à deux incomparables selon un ordre donné. Dans la théorie des automatescertains algorithmes utilisent les antichaines comme structures de données afin de stocker des ensembles d'états d'un automate tous disjoints. Par exemple elles sont utilisées dans des algorithmes de simulation utilisés pour la simplification de l'automate. L'implémentation d'une antichaine consiste à toujours vérifier que les éléments insérés dans l'antichaine ne sont pas comparables à un déjà présent, ce qui rend coûteux l'opération d'insertion car il faut faire à chaque fois un parcours linéaire des données. Dans ce rapport, nous proposons différents algorithmes pour implémenter l'antichaine en optimisant l'insertion d'un élément. Nous présenterons ensuite les résultats de ces implémentations avec le model checker Spot pour pouvoir comparer leurs performances.