J. Mairesse
LIAFA, CNRS
(travail réalisé avec S. Gaubert)
On introduit un modèle généralisant la représentation des monoides de trace a l'aide de tas de pièces (Viennot 86). Intuitivement, il s'agit d'empiler (a la `Tetris') des pièces de formes polyominales. On représente le comportement des réseaux de Petri 1-bornés temporisés a l'aide de ce modèle. On obtient ainsi une généralisation au cas temporisé de la modélisation (Mazurkiewicz 77), du comportement logique d'un réseau de Petri 1-borné à l'aide de langages de trace.
En utilisant la représentation par tas de pièces comme point de
départ, on propose divers résultats
d'évaluation de performance: comportements asymptotiques en moyenne,
dans le pire et dans le meilleur des cas.
En particulier, on propose des algorithmes permettant de calculer
l'ordonnancement dans le pire des cas (tas de pièces dont la taille
croit le plus vite), ainsi que celui dans le
meilleur des cas (tas de pièces dont la taille
croit le plus lentement) si les hauteurs des pièces sont rationelles.
On montre comment ces resultats s'étendent au cas ou l'on se restreint
a considérer les ordonnancements appartenant a un language rationnel
ou algébrique.