Name
Abstract | ||
|---|---|---|
Dans les structures d'événements, un des modèles classiques du parallélisme, intervient la notion d'étiquetage agréable: celle-ci consiste à attribuer une étiquette à chaque événement de la structure de sorte que deux événements peuvent porter la même étiquette, dès qu'ils sont dans une relation de causalité temporelle ou qu'ils ne concernent pas les occurences initiales de deux actions incompatibles dans de déroulement d'un calcul. Le problème est ici de déterminer le nombre minimum d'étiquettes. Nous nous intéressons plus particulièrement aux structures d'événements admettant un étiquetage agréable fini. Nous caractérisons celles qui admettent un étiquetage agréable sur deux lettres. Mais nous démontrons qu'en général dans le cas fini l'optimisation du nombre d'étiquettes est un problème NP-difficile. Enfin l'utilisation d'outils soit combinatoires, soit issus de la théorie de l'ordre permet d'étudier quelques cas particuliers. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0304-3975(94)90065-5 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
event structure,finite labelling problem | Journal | 123 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 9 |
PageRank | References | Authors |
0.57 | 1 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marc Roland Assous | 1 | 11 | 0.97 |
| Vincent Bouchitté | 2 | 172 | 12.07 |
| Christine Charretton | 3 | 11 | 0.97 |
| Brigitte Rozoy | 4 | 151 | 15.79 |