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 |
+ | | resume = Dans la théorie des ordres, une antîchaine est un sous-ensemble d'éléments tous deux à deux incomparables selon un ordre donné. Dans la théorie des automatescertains algorithmes utilisent les antîchaines 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 antîchaine consiste à toujours vérifier que les éléments insérés dans l'antîchaine 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'antîchaine 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 |
||
Revision as of 14:45, 18 June 2018
- Auteurs
- Arthur Remaud
- Type
- techreport
- Année
- 2018
- Numéro
- 1803
Résumé
Dans la théorie des ordres, une antîchaine est un sous-ensemble d'éléments tous deux à deux incomparables selon un ordre donné. Dans la théorie des automatescertains algorithmes utilisent les antîchaines 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 antîchaine consiste à toujours vérifier que les éléments insérés dans l'antîchaine 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'antîchaine 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.