Difference between revisions of "Publications/remaud.18.seminar/fr"
From LRDE
| Line 4: | Line 4: | ||
| year = 2018 |
| year = 2018 |
||
| number = 1803 |
| number = 1803 |
||
| − | | resume = Dans la théorie des ordres, une antichaîne est un sous-ensemble d'éléments tous deux à deux incomparables selon un ordre donné. Dans la théorie des |
+ | | resume = Dans la théorie des ordres, une antichaîne est un sous-ensemble d'éléments tous deux à deux incomparables selon un ordre donné. Dans la théorie des automates, certains algorithmes utilisent les antichaînes 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 antichaîne consiste à toujours vérifier que les éléments insérés dans l'antichaîne 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'antichaîne 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. |
| type = techreport |
| type = techreport |
||
| id = remaud.18.seminar |
| id = remaud.18.seminar |
||
Latest revision as of 15:00, 3 July 2018
- Auteurs
- Arthur Remaud
- Type
- techreport
- Année
- 2018
- Numéro
- 1803
Résumé
Dans la théorie des ordres, une antichaîne est un sous-ensemble d'éléments tous deux à deux incomparables selon un ordre donné. Dans la théorie des automates, certains algorithmes utilisent les antichaînes 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 antichaîne consiste à toujours vérifier que les éléments insérés dans l'antichaîne 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'antichaîne 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.