dit ``(max,+)'' ou le semianneau
,
dit ``tropical'') ont été introduits
indépendamment par diverses communautés.
ALGÈBRES TROPICALES ET APPLICATIONS
AUX SYSTÈMES À ´EVÉNEMENTS DISCRETS
ET À LA COMMANDE OPTIMALE
RAPPORT FINAL D'ACTIVIT´E : 1996-2000
CM
T´EL : 01 45 52 54 30 (ENSTA) 01 39 63 52 58
(INRIA)
FAX : 0 39 63 57 86
E-MAIL : STEPHANE.GAUBERT@INRIA.FR
T´EL : 02 40 37 69 67
FAX : 02 40 37 69 30
E-MAIL : LOISEAU@IRCCYN.EC-NANTES.FR
Les semianneaux dont l'addition est idempotente (comme le semianneau
dit ``(max,+)'' ou le semianneau
,
dit ``tropical'') ont été introduits
indépendamment par diverses communautés.
- En Automatique, ils interviennent d'abord comme un outil pour la modélisation, l'analyse, l'évaluation de performance et la synthèse de lois de commande pour des classes bien répertoriées de systèmes à événements discrets déterministes ou stochastiques (ateliers flexibles, réseaux de transport, réseaux de communications, systèmes multi-processeur, etc.), et comme un formalisme algébrique particulièrement approprié pour la commande optimale et l'optimisation des systèmes. Ils apparaissent aussi dans les questions méthodologiques et algorithmiques, qu'il s'agisse de trouver une solution ou d'analyser sa complexité.
- En Informatique Théorique, le semianneau tropical a joué un rôle clé dans la résolution de problèmes classiques en théorie des langages et des automates (problèmes de décision, mesure de la complexité non-déterministe des automates). Il continue a faire l'objet de travaux très actifs.
- Ces algèbres exotiques sont aussi apparues naturellement dans divers domaines des mathématiques. Ainsi, les systèmes dynamiques linéaires dans l'algèbre max-plus appartiennent à la théorie de Perron-Frobenius non-linéaire, qui s'intéresse aux opérateurs monotones opérant sur des cônes. Ces algèbres interviennent aussi dans le calcul de certaines asymptotiques. Ainsi, la détermination de la phase quasi-classique de l'équation de Schrödinger, les asymptotiques à température nulle en mécanique statistique, ou la théorie des grandes déviations, font intervenir des problèmes limites qui sont des problèmes de commande optimale ou d'optimisation du type de ceux traités en Automatique, et qui relèvent d'une même théorie de l'Analyse Idempotente.
L'objectif affiché lors de la création du groupe de
travail ``Algèbres Tropicales ...'', était de ``parvenir à
une communauté de vues entre les écoles développant la théorie
et les applications des semianneaux dont l'addition est idempotente.''
Par communauté de vues, on entendait un état de l'art collectif sur la question. Il s'agissait de recenser et d'unifier les résultats existants, tant sur le plan de la compréhension théorique que du calcul effectif (algorithmes et logiciels). On entendait aussi une confrontation des motivations et problématiques propres à chaque école (catalogue des problèmes ouverts, des exemples et des applications), conduisant à l'identification et a l'attaque de problèmes d'intérêt commun, et tout particulièrement, au traitement des applications des uns à l'aide des outils des autres.
Cette action lancée en 1996 était de nature prospective, sur un horizon court. Il s'agissait d'abord de se rencontrer, d'évaluer les possibilités de fertilisation croisées, et de diffuser les résultats. L'action a étée reconduite pour 2 ans fin 1998, le ministère de l'Education Nationale, de la Recherche et de la Technologie nous attribuant un financement pour les années 1999-2000.
Il est donc temps de faire un bilan aussi complet que possible des activités qui ont été menées dans le groupe. Des bilans intermédiaires à mi-parcours avait déja été fait aux mi-97 [177] et mi-99 [185].
Stéphane Gaubert, Chargé de Recherche INRIA, INRIA-Rocquencourt et LMA ENSTA,
Jean Jacques Loiseau, Chargé de Recherche CNRS, IRCCyN.
La partie française de la communauté scientifique intéressée relève en bonne part de l'Automatique (Analyse et Commande des Systèmes, Programmation Dynamique), de l'Informatique (Automates, Théorie des Langages), ou de thèmes à l'intersection précise des deux disciplines (Systèmes à Événements Discrets). C'est pourquoi le groupe a été rattaché au PRC/GdR AMI (puis ALP), d'une part, au PRC/GdR Automatique, d'autre part. Le thème est à la croisée de plusieurs disciplines: ont trouvera aussi dans la liste des participants des chercheurs intéressés par les aspects purement mathématiques. Il y a eu aussi à quelques occasions des intervenants ou auditeurs d'autres disciplines (e.g. physique statistique, gestion de la production).
Le noyau du groupe est d'environ 30 personnes, venant très régulièrement. Outre ce noyau, il y a un groupe variable de personnes qui viennent occasionnellement, suivant la coloration thématique de la réunion, et aussi, pratiquement à chaque réunion, de nouveaux auditeurs, désireux de s'informer du sujet. En tout, l'audience des réunions ordinaires a tourné entre 30 et 45-50 personnes, avec une moyenne a 40.
Les participants du groupe proviennent des laboratoires suivants (sont listés les participants aux réunions depuis 98).
,
Professeur, Université de Caen.Neuf réunions du groupe de travail ont déja eu lieu, qui rassemblent de 30 à 50 participants :
| 1. | les 6-7 juin 1996, |
2. |
le 21 octobre 1996, |
3. |
le 2 décembre 1996, |
4. |
le 17 mars 1997, |
5. |
le 25 juin 1997, |
6. |
les 3-4 décembre 1997, |
7. |
les 25-26 novembre 1998, |
8. |
Les 29-31 mars 1999, |
9. |
Le 15 décembre 1999. |
Grâce à à l'hospitalité de nos collègues du LIAFA, les 6 premières réunions ont eu lieu à Jussieu. Les 3 suivantes se sont tenues à l'ENS Paris. Outre ces réunions, le groupe de travail a contribué à un certain nombres d'événements (École de Printemps, sessions invitées, Workshops INTAS et MADDES), détaillés plus bas. En outre, la reunion de mars 1999, qui avait le label de ``journées thématiques du GdR Automatique'', était organisée conjointement avec le projet TMR ``ALAPEDES'' (The ALgebraic Approach to Performance Evaluation of Discrete Event Systems) de la Communauté Europeenne. Elle a rassemblé environ de 65 participants, dont un tiers de chercheurs étrangers. La réunion finale du groupe sera le Workshop IFAC de Prague en août 2001.
Les programmes de ces réunions figurent en annexe (Annexe 3).
La programmation des réunions inclut des exposés spontanément proposés par les membres du groupe, en particulier lors de discussions ouvertes sur la programmation menées fréquemment pendant les réunions. Il y a eu aussi beaucoup d'interventions ``provoquées'' par les organisateurs afin de répondre harmonieusement à la politique scientifique affichée lors du lancement du groupe. La philosophie qui à été pratiquée en la matière peut se résumer aux principes suivants.
Faire un ``cours permanent'' De nombreux
exposés de synthèse ont été sollicités sur des sujets
très variés (G. Cohen, S. Samborskii, J.-E. Pin à la
réunion 1; J. Sakarovitch, M. Gondran à la réunion 2, Ph.
Chrétienne, F. Baccelli et D. Krob à la réunion 3, M.
réunion 4, S. Samborskii à la réunion 5, J. Sakarovitch
à la réunion 6, C. Choffrut, B. Derrida, P. Gastin lors de la
réunion 7, C. Dellacherie, C. Commault, lors de la réunion 8, G.
Hansel, J.C. Hennet lors de la réunion 9). Le but ici est en
particulier de faciliter l'accès des réunions aux nouveaux
auditeurs (doctorants, simples curieux, etc).
Faire à l'occasion des travaux dirigés
qui permettent aux
auditeurs de maitriser et réutiliser a leur propre compte les
techniques exposées mieux qu'un simple expose scientifique
habituel (J.E. Pin à la réunion 1, d'autres ont été
organisé lors de l'École de
printemps d'Informatique Théorique).
Donner la parole aux jeunes Une grande part
du travail scientifique effectif se fait dans les thèses. Le
groupe de travail est une tribune pour les thésards et jeunes
chercheurs qui viennent exposer les travaux de recherche significatifs
les plus récents (E. Menguy à la réunion 3, J. Mairesse
à la réunion 5, D. Hong lors de la réunion 6, B.
Cottenceau, I. Klimann, et J. Assan lors de la réunion 7, Les
doctorants et post-doctorants du réseau Alapedes lors de la
réunion 8).
Donner la parole aux visiteurs
étrangers R. Bapat à la réunion 1, plusieurs
intervenants de l'École de printemps et des Journées
Thématiques. Notons que des collègues étrangers se
trouvent assez souvent dans l'assistance, dans quelques cas,
invités sur les fonds du groupe de travail (V. Kolokolt'sov,
P. Butkovic, F. Bellalouna,
L. Farina, ont ainsi été invités en 1998 et 1999).
Faire des réunions thématiques
Plusieurs demi-journées thématiques ont été
organisées, ce qui permet précisément de confronter les
différents points de vue sur une même question. Ainsi, la
réunion 3 avait pour thème: ``combinatoire des empilements,
semianneau (max,+), et systèmes à événements discrets
stochastiques'' la réunion 4 comprenait une demi-journée
``Algèbre max-plus et Optimisation'', la réunion 5 comprenait
plusieurs exposés sur les questions algorithmiques et les outils
logiciels développés ou en cours de développement. La
réunion 9 a été entièrement consacrée aux
systèmes positifs, et la prochaine réunion (début 2001)
aura sera centrée sur les calculs de borne dans les processus
aléatoires et les réseaux de communication.
Explorer les applications en matière de morphologie
mathématique (J. Mattioli, réunion 2), de traitement de
l'incertitude (H. Prade, réunion 2), d'ordonnancements (Ph.
Chrétienne, réunion 3), d'informatique temps-réel (A.
Benveniste, réunion 5), de génome (J.-P. Comet lors de la
réunion 7), de réseaux de communications (T. Bonald lors de la
réunion 8) ou de transports (R.J. van Egmond, réunion 8).
Traiter de façon exhaustive le champ thématique , en
particulier en présentant systématiquements les résultats
récents en matière de modélisation, d'analyse et commande
de systèmes à événements
discrets, d'algèbre de base, et en explorant
les liens avec des disciplines proches
(par exemple à l'occasion de l'exposé introductif
de B. Derrida, à la réunion 7, sur
des problèmes de Physique Statistique
ou interviennent l'algèbre max-plus,
ou de l'exposé de M. Artzrouni à la réunion
Bilan, sur des problèmes d'inspiration démographique).
La 26-ième édition de l'École de Printemps d'Informatique Théorique relative aux ``Algèbres Max-Plus et applications en Informatique et Automatique'' a été organisée par S. Gaubert (INRIA Rocquencourt), J.J. Loiseau (IRCyN, Nantes), J. Mairesse (LIAFA), J.E. Pin (LIAFA), M. Nivat (LIAFA) à Noirmoutier, du 4 au 7 mai 1998. L'École était organisée conjointement par l'INRIA, le LIAFA, le CNRS et l'IRCyN avec le soutien de la formation permanente du CNRS, de l'INRIA, du projet européen ALAPEDES, du programme EC TMR de la communauté européenne, du GDR Automatique (CNRS), du conseil régional des pays de la Loire et d'EDF. Cette école a réuni environ 65 chercheurs dont un tiers de jeunes chercheurs (avant la thèse) et un tiers de chercheurs confirmés. Elle réunissait en particulier les meilleurs spécialistes européens du domaine.
Le but de l'école était de presenter les résultats algébriques issus du formalisme de l'algèbre Max-Plus et d'autre part de montrer aussi, en particulier à partir de l'étude de cas concrets (ateliers flexibles, réseaux de transport,...), comment ces structures fournissent une compréhension intuitive et des outils efficaces de calcul, pour certaines classes d'applications. les cours étaient complétés par trois scéances de travaux dirigés, et une scéance de démonstration des logiciels existants.
Le programme de l'école figure en annexe (Annexe 2). Les supports de cours distribués aux participants (501 pages) constituent une présentation assez complète des résultats du domaine. Une bonne partie de ces textes sont des contributions originales et didactiques : ils figurent dans la liste des contributions (de [141] à [150]).
S. Samborski a organisé à Caen, les 26-27 février 1999, un Workshop INTAS sur l'Analyse Idempotente et ses Applications. Participaient au workshop: G.Litvinov, G. Chpiz, I.Andreeva (Internat.Sophus Lie Center, Moscou), A.Tchurkine (Université de Moscou), V. Belavkin (University of Nottingham, UK), V.Kolokoltsov, A. Tyukin (Trent University of Nottingham ,UK), M. Akian, S. Gaubert (INRIA).
Dans le cadre de l'action de recherche coopérative MADDES de l'INRIA. Bruno Gaujal, E. Altman, et S. Gaubert ont organisés à Sophia-Antipolis, les 28-29 octobre 1999, le workshop ``Programmation Dynamique et Systèmes à Événements Discrets'', avec le soutien du groupe ``Algèbres Tropicales ...''. Il s'agissait de rassembler les chercheurs en décision markovienne (ce qui inclut notamment la programmation dynamique, le contrôle stochastique, la théorie des jeux) et en systèmes à événements discrets (déterministes ou stochastiques, commande et évaluation de performances) afin de confronter les approches et les points de vue.
Des sessions invitées dans des conférences internationales ont été organisées par des membres du groupe de travail, notamment à la Mediteranean Conference on Control and Automation de Chania, en Crète (MSCA'97), à la European Control Conference de Bruxelles (ECC'97) et à la Conférence IFAC on System Structure and Control de Nantes (IFAC SSC'98). Le programme de ces 4 sessions figure dans l'Annexe 1.
À la suite de l'École de printemps de Noirmoutier, un numéro spécial de la revue Theoretical Computer Science (TCS) a été lancé, destiné à recueillir les contributions récentes (mais souvent trop pointues pour avoir leur place dans l'École de Printemps dont l'objectif était plus didactique) dans le domaine. S. Gaubert, J.J. Loiseau, J. Mairesse et J.E. Pin ont préparés ce numéro, en tant qu'éditeurs invités.
Le sommaire de ce numéro spécial apparait dans la liste des publications ([46] à [56]).
Citons quelques cours dispensés sur les thèmes d'intérêt du groupe de travail:
-- Algèbre (max,+) et systèmes à événements
discrets, Cours/TD de 12 h, par Jean-Louis Boimond,
en DESS
"Automatique des Systèmes Complexes" de l'ISTIA d'Angers. Il a
pour ambition de présenter l'intérêt d'étudier les
systèmes à événements discrets à travers
l'algèbre (max, +), en particulier, relativement à
l'évaluation de performances de certains systèmes de
production.
-- Commande des systèmes à événements discrets,
Cours/TD, 25 h, DEA
"Automatique et Informatique Appliquée" de l'Ecole Centrale de
Nantes et de l'Université de Nantes, par J.-L. Boimond et E.
Wagneur (pour la moitié ``Algèbre max-plus''), J.-L.
Ferrier et J.J. Loiseau (pour le seconde moitié, ``Langages
commandables'').
-- Cours sur les Systèmes dynamiques à événements
discrets, cours commun École des Mines & DEA Automatique et
Traitement du Signal Orsay, 21 heures, de S. Gaubert.
-- Une filière réseaux et systèmes
à événements discrets a été créée par Francois Baccelli
dans le DEA Algorithmique (ENS/X/Paris 6-7-11/ENST). Elle est constituée de
trois cours de 20 h : I- Méthodes algébriques pour les systèmes
à événements discrets déterministes, II- Méthodes
algébriques pour les systèmes à événements discrets,
extensions non-linéaires et stochastiques, III- Analyse
markovienne, qui sont dispensés par F. Baccelli, S.
Gaubert, B. Gaujal, A. Jean-Marie et J. Mairesse.
Le serveur du groupe (http://amadeus.inria.fr/TROPICAL/) fonctionne depuis mai 1996. C'est une vitrine du groupe, et un outil efficace pour diffuser les programmes de réunion, les résumés ou publications associés. Ce serveur est largement consulté, en particulier par des chercheurs étrangers qui viennent y chercher des informations sur le domaine.
Des logiciels sont développés ou en cours de développement, en particulier en relation avec le réseau EC-TMR ALAPEDES, dans les domaines intéressant le groupe de travail (évaluation de performance de Systèmes à événements discrets, de Réseau de Petri temporisés, analyse spectrale de matrices max-plus, calcul d'expressions de séries formelles, d'automates, monoïdes).
Quatre logiciels existent:
-- la boite à outils
max-plus de SCILAB (developpée par le groupe
Max-Plus, INRIA,ENPC, ENSTA), téléchargeable
dans la section contrib du site de scilab
http://www-rocq.inria.fr/scilab/
-- Semigroupe (Jean-Éric Pin). Semigroupe
permet de calculer rapidement de très gros semigroupes finis
(par exemples, semigroupes de transformations,
semigroupes de matrices sur divers semi-anneaux,
dont max-plus), et determine en particulier leur structure en classes
de Green.
-- ERS, une librairie d'évaluation de performance
de systémes à événements discrets,
développée par A. Jean-Marie:
http://www-sop.inria.fr/mistral/soft/ers.html.
ERS contient des interfaces graphiques en tcl/tk permettant
de simuler réseaux de Petri et tas de pièces,
ainsi que des algorithmes à base d'algèbre max-plus
(valeur propre, bornes d'exposants de Lyapunov)
Une formation de 2 jours
autour de Scilab, ERS, et Semigroupe,
a été organisée par G. Cohen et J.-P. Quadrat les 18 et 19
Juin 1998 à l'INRIA Rocquencourt, avec le concours
de plusieurs membres du groupe tropical
et du réseau ALAPEDES.
-- Librairie c++ pour la manipulation
de séries périodiques dans les dioïdes de séries formelles
(Windows/Linux), développée par l'équipe d'Angers. Accès à :
http://www.istia.univ-angers.fr/ hardouin/outils.html
L'activité du groupe de travail va se cloturer par une réunion plus ouverte avec actes (c'était l'engagement pris lors du renouvellement du groupe de travail fin 1998), le ``Workshop on Max-Plus Algebras and Applications to Discrete-Event Systems, Computer Science, and Optimization'' organisé à Prague du 29-31 août 2001.
Le programme devrait comporter une quarantaine de présentations,
pour moitié dans le cadre de 6 sessions invitées :
-- Optimisation combinatoire, organisée par K. Zimmermann
(U. Charles, Prague),
-- Systèmes à Événements discrets, organisée par
F. Baccelli.
-- Fonctions nonexpansives, organisées
par C. Sparrow (Cambridge).
-- Théorie des automates, organisée par J.-É. Pin,
-- Analyse Idempotente, organisée par S. Samborski,
-- Mesures non-additives et mesures idempotentes,
organisée par E. Pap (Novi Sad).
Un objectif important de ce workshop est d'établir des liens avec les collègues des ex-pays de l'est, et en particulier de Slovaquie, République Tchèque, Yougoslavie, Russie où on trouve des collègues prestigieux qui sont des précurseurs en matière d'Algèbres Tropicales (V. Maslov, E. Pap, K. Zimmermann), et qui ont fondé des Écoles de pensée très actives dans le domaine.
Le site du workshop est
A titre individuel, les membres du groupe de travail ont publiés 30 articles de revues, 10 chapitres de livres, plus de 50 communications à des conférences. Il y a peu de travaux en commun de membres du groupe, mais de plus en plus de travaux sont influencés par les sujets qui ont été exposés au groupe de travail; les échanges d'idées deviennent courants, en particulier entre Automaticiens et Informaticiens.
Près de 20 DEA et Thèses, et aussi un mémoire d'habilitation (voir la liste de publications ci-jointe, de [151] à [169]) ont été encadrées sur des thèmes du groupe de travail. Ce sont ces travaux de thèses qui ont provoqués le plus de travaux communs et de rapprochements entre équipes. Le groupe de travail a notamment financé des réunions de travail entre les groupes de Roquencourt et d'Angers, lors de la thèse d'Éric Menguy, et entre les groupes de Jussieu et de Nantes, à propos des thèses de Jean Assan et d'Inès Klimann.
Les taille des réunions ordinaires du groupe (30-45 personnes) rend difficile le vrai travail technique en commun. Ainsi, des groupes plus petits se sont crées naturellement.
-- Depuis la rentrée 1997 s'est constitué au LIAFA un groupe de travail transversal, sur le thème ``Systèmes à événements discrets'', à l'intersection des trois équipes de recherche du laboratoire, animé par Jean Mairesse. Les recherches menées au sein de cet axe transversal se sont concrétisées par la réunion chaque quinzaine d'un groupe de travail auquel participent des membres des 3 équipes du LIAFA (C. Choffrut, P. Gastin, D. Krob, J.-E. Pin, P. Weil, M. Kanta, L. Viennot) et aussi des membres extérieurs (S. Gaubert). En 1999, ce groupe s'est élargi à l'équipe de l'INRIA Rocq. et à celle de l'ENS, avec pour programme: étude du livre de Högnäs et Mukherjea sur les marches aléatoires dans les semigroupes (animé par J. Mairesse), étude du livre de Chang et des applications à l'évaluation du protocole TCP (animé par F. Baccelli).
-- A Nantes, une nouvelle équipe de recherche sur le thème
``Analyse et Commande des Systèmes à Événements
Discrets'' est crée en 1999, elle était en gestation depuis
96 et fonctionne depuis 98.
Le groupe de Travail ``Algèbres Tropicales ...'' a financé des déplacements de chercheurs désireux de travailler ensemble. Ce mode de travail a été privilégié en 2000, dans le but de pérenniser les contacts pris entre les communautés (c'était aussi un des engagements pris envers le GdR à la mi-99).
-- Au cours des thèse d'Éric Menguy, de Bertrand Cottenceau et
Sebastien Lahaye, des échanges ont eu
lieu entre les groupes d'Angers et de Rocquencourt, sur certaines
propriétés algébriques utilisées dans le cadre de la
commande de systèmes max-plus linéaires. Ces échanges
ont été très fructueux, une véritable école dans
ce domaine a émergé à Angers.
-- Dans le cadre des thèses de Jean Assan et
d'Inès Klimann, des échanges ont eu lieu entre Nantes (J.
Assan, J.J. Loiseau), le LIAFA (I. Klimann, J.-E. Pin) et le Labri (P.
Weil) sur le thème du calcul de certains éléments
extrémaux dans des demi-treillis (en particulier ceux
utilisés en Automatiques: espaces ou modules (A, B)-invariants,
langages commandables, liés à l'utilisation de certaines
classes d'opérateurs, systèmes à retards ou fractionnaires
notamment). Cela a permis a Jean Assan de mieux formaliser certains
problèmes de convergence d'algorithmes et de la calculabilité
de la limite [167]. Inès Klimann a introduit un nouveau
type d'automates --et un nouveau critère de
reconnaissabilité-- pour certaines séries (A,
B)-invariantes ou définies par des équations aux points
fixes [168]. Ces contacts se poursuivent.
-- Enfin des échanges ont eu lieu entre Nantes
(E. Wagneur) et Rocquencourt (G. Cohen, S. Gaubert, J.P. Quadrat) pour
discuter de questions d'algèbre de base touchant aux
semi-modules, questions auxquelles les deux équipes se sont
intéréssées depuis longtemps (somme directe, projections,
analogue des suites exactes, etc). Ce thème a fait l'objet de
publications séparées [96,97,104].
-- Un sous-groupe ``calcul de bornes'' s'est
constitué en 2000, sur le thème du développement de
méthodes de comparaison de processus aléatoires --et de
simplification de modèles-- en vue
d'évaluation de performances et d'analyse du comportement
transitoire, et d'applications notamment en réseaux de
communications et analyse de fiabilité. La prochaine réunion
du groupe de travail sera centrée sur ce thème.
| Nature de la dépense | Montant (kF) |
| Réunion 1 | 6,0 |
| Réunion 2 | 3,2 |
| Réunion 3 | 7,4 |
| Réunion 4 | 7,5 |
| Réunion 5 | 13,2 |
| Réunion 6 | 14,8 |
| Réunion 7 | 10,0 |
| École de Printemps | 7,0 |
| Réunion 8 frais | 10,0 |
| Réunion 8 missions | 15,0 |
| Réunion 9 | 7,4 |
| Réunions de travail | 23,9 |
| Invitations de chercheurs étrangers | 16,6 |
Total des dépenses |
142,0 kF |
Recettes
| Nature | Montant |
| GdR-PRC AMI, 1996 | 16,6 |
| GdR-PRC Automatique, 1997 | 41,5 |
| GdR-PRC Automatique, 1998 | 41,5 |
| GdR-PRC Automatique, 1999 | 10,0 |
| MENRT, 1999 pour 1999-2001 | 84,0 |
| Total | 193.6 kF |
Il nous reste 51,6 kF pour 2001, que nous comptons utiliser à:
- organiser 1 réunion ``calcul de bornes''
- financer des réunions de travail en sous-groupe.
- inviter certains collègues des pays de l'est au Workshop de Prague,
3450, July 1998, and
C.R.A.S, Vol. 327, série I, 927-932, 1998.
control, Special issue On
Max-Plus Algebras, à paraître.
control,
Rapport interne i3s, UNSA/CNRS
Soumis a TCS, special issue on max-plus algebras.
Session NEW TRENDS IN DISCRETE-EVENT SYSTEMS
Organisée by J. J. Loiseau à MSCA'96, Chania, Crète.
[1] F. Baccelli (INRIA, France) and B. Gaujal (INRIA, France),
Logical properties through timed Evolution Equations.
[2] G. Mauroy (Georgia Tech, USA) and Y. Wardi (Georgia Tech, USA),
=ault diagnosis in production systems based on timed Petri nets.
[3] J.M. Prou (Univ. Nantes, France) and E. Wagneur
(Ecole des Mines de Nantes, France),
Decomposition of periodic series.
[4] O. Roux (Institut Universitaire, France) and V. Rusu (LAN, France),
Verifying real-time systems with decidable hybrid automata.
[5] M. P. Spathopoulos (Univ. Strathclyde, Great Britain),
Control design for DES.
[6] D. Tacconi (Univ. Texas, USA), F. L. Lewis (Univ. Texas, USA) and
H. -H. Huang (Univ. Texas, USA),
Modeling and simulation of discrete event systems using
a matrix formulation.
[7] K. C. Wong (CWI, Netherlands) and W. M. Wonham (Univ. Toronto, Canada),
Modular control and coordination of discrete-event systems.
Organisée par B. Gaujal à ECC'97,
Bruxelles.
[1] B. Gaujal (INRIA, France), Infinite behavior of continuous and
discrete nets.
[2] S. Gaubert (INRIA, France) and J. Mairesse (LIAFA-CNRS, France),
Modeling and analysis of timed Petri nets using heaps of pieces.
[3] J.M. Vincent (LMC-IMAG, France), On the (max, +) structure of
reservation systems.
[4] Subiono and G.J. Olsder (Delft Univ., Holland), On bipartite
min-max-plus systems.
[5] A. Lüder, U. Anderssohn, and H.M. Hanisch (Magdeburg Univ,
Germany), Logic controller synthesis for net condition/event systems
with forbidden paths.
[6] B. De Schutter and B. De Moor (ESAT-SISTA, Belgium), The QR
decomposition and the singular value decomposition in the symetrized
max-plus algebra.
Organisée par L. Libeaut à IFAC Conf. SSC'98, Nantes.
J.E.R. Cury (Bra), and B.H. Krogh (USA), Supervisor Synthesis for Discrete
Event Systems with Finite and Infinite Specifications.
S. Takai (J), Maximally Permissive Robust Supervisors
for a Class of Specification Languages.
M.D. DiBenedetto, A. Sangiovanni-Vincentelli, and A. Saldanha (I),
Asymptotic model matching for finite state machines.
M.R. Laurence, and M.P. Spathopoulos (UK), Computing
the Untimed Language of a Buechi Timed Automaton.
B.A. Brandin (D), Supervisory control and routing of
batch processes with just-in-time constraints based on
timed discrete event systems.
O. Maler (F), Controller Synthesis for Hybrid Systems.
Organisée par S. Gaubert et J.J. Loiseau
à IFAC Conf. SSC'98, Nantes.
G.J. Olsder and Subiono (NL),
On large scale max-plus algebra models in railway systems.
E. Altman (F), B. Gaujal (F), A. Hordijk (NL), Regular Sequences and
Admission Control in Stochastic (max,+) Systems.
G.J. Olsder (NL), and S. Perennes (F), The upper bound on
the period of non-expansive mappings.
J. Cochet-Terasson (F), G. Cohen(F), S. Gaubert (F), M. McGettrick
(F), and J.P. Quadrat (F), Numerical computation of spectral
elements in max-plus algebra.
E. Wagneur (F), Duality in the max-algebra.
S.N. Samborski (Ru), Evolutions Determined by Control
Problems and Hamilton-Jacoby-Bellman Equations.
09h20-09h30 Introduction, M. Nivat;
09h30-10h00 Algèbre max-plus, semi-anneaux et dioïdes : le début d'une histoire, M. Gondran (EDF Clamart);
10h00-11h00 Semi-anneaux idempotents : résultats de base illustrés, S. Gaubert (INRIA Rocquencourt);
11h30-12h30 Théorie spectrale max-plus, S. Gaubert;
15h30-17h40 Introduction to timed discrete event systems, G.J. Olsder (TU Delft, The Netherlands);
18h00-19h00 Travaux dirigés : Modélisation algébrique et évaluation de performance de systèmes a événements discrets (exemples simples d'ateliers).
09h00-11h10 Introduction aux séries rationnelles et aux automates, J. Berstel (Univ. Marne-la-Vallée);
11h30-12h30 Applications of the max-plus algebra to time tables of railway systems and to synchronization of traffic lights, G.J. Olsder;
15h30-16h30 Résiduation et applications, G. Cohen (CAS, ENSMP);
16h40-17h40 Regularity of matrices, assignment problems, time-complexity, P. Butkovic (Univ. Birmingham, UK);
18h00-19h00 Travaux dirigés : Automates et séries.
9h00-10h30 Représentations externes des systèmes, G. Cohen;
11h00-12h30 Systèmes max-plus linéaires aléatoires, F. Baccelli (INRIA Sophia Antipolis);
15h30-16h30 Automates max-plus, réseaux de Petri 1 - bornés et ordonnancement, J. Mairesse;
16h40-17h40 Tour d'horizon des outils logiciels en algèbre max-plus;
18h00-19h00 Travaux dirigés : Représentation de systèmes a ressources partagées, ordonnancement
09h00-10h00 The tropical semiring and decidable problems, I. Simon (Univ. Sao-Paulo, Brasil);
10h10-11h10 The tropical semiring and undecidable problems, I. Simon;
11h30-12h30 Dualité entre le calcul des probabiliés et l'optimisation, J-P. Quadrat (INRIA Rocquencourt);
14h00-15h00 Commande de SED - Théorie des langages commandables, L. Libeaut (IRCyN);
15h10-16h10 Max-plus algebra and non-expansive maps, J. Gunawardena (BRIMS, Hewlett-Packard Labs, UK);
16h10 Fin des cours.
| 9h30 | Stéphane Gaubert, | Bienvenue |
| Jean-Jacques Loiseau | ||
9h40 |
Guy Cohen | Dioïdes et systèmes à événements discrets |
| 11h10 | Pause | |
| 11h30 | Serguei Samborskii | Analyse idempotente |
| 13h | Pause dejeuner | |
| 14h30 | Jean-Eric Pin | Semi-anneaux tropicaux |
| 16h | Pause | |
| Session: travaux en cours, | ||
| 16h20 | questions ouvertes, | |
| présentation d'équipes... | ||
| Jean-Louis Boimond | Commande de systèmes max-plus | |
| Calcul de temps d'exécution parallèle et de taux de | ||
| Stéphane Gaubert | production: quelques remarques et problèmes en suspens. | |
| Jean Jacques Loiseau | Modèle Max-Plus des réseaux de Petri | |
| Discussion sur le | ||
| 17h30 | fonctionnement et la vie | |
| du groupe. |
| 9h | Bruno Gaujal | Representation minimale d'equations de recurrence |
| uniformes | ||
9h50 |
François Baccelli | Equations d'évolution et propriétés logiques |
| des réseaux a choix libres | ||
| 10h40 | Pause | |
| 11h00 | Jean-Eric Pin | TD d'initiation au semi-anneau tropical |
| 13h00 | Pause dejeuner | |
| 14h30 | Edouard Wagneur | Algèbre max-plus : Une approche géométrique |
| 15h30 | Ravindra Bapat | Permanents, max algebra and optimal assignment |
| 9h30 | Jacques | Rationalité & reconnaissabilité : une introduction |
| Sakarovitch | ||
| 11h00 | Pause | |
| 11h20 | Michel Gondran | Analyse Min Plus et Analyse Min Max |
| 12h50 | -- | Discussion (vie du groupe, programmation des réunions suivantes). |
| 13h00 | Pause déjeuner | |
14h30 |
Juliette | Base génératrice minimale d'une ouverture morphologique |
| Mattioli | ||
| 15h30 | Pause | |
| 15h50 | Henri Prade | Algèbres tropicales et traitement de l'incertitude |
| 17h20 | Fin de réunion |
| 9h30 | Philippe | Un survey sur l'ordonnancement cyclique |
| Chretienne | ||
| 11h00 | Pause | |
11h20 |
François Baccelli | Méthodes algébriques pour les systèmes |
| à événements discrets stochastiques | ||
| 12h50 | -- | Discussion (vie du groupe, programmation des réunions suivantes). |
| 13h00 | Pause déjeuner | |
| 14h30 | Daniel Krob | Empilements et monoides de trace |
| 16h00 | Pause | |
| 16h20 | Jean-Marc Vincent | Comportement dynamique de systèmes de réservation stochastiques |
| 17h20 | Fin de réunion |
| 9h30 | Marianne | Des probabilités à l'optimisation: algèbre et grandes déviations |
| Akian | ||
| 11h00 | Pause | |
| 11h20 | Pierre | Frayeur mathematique comme alternative a l'Esperance mathematique |
| Bernhard | ||
| 12h20 | -- | Discussion. |
| 14h30 | Jean-Eric Pin | Reconnaissance des ensembles de mots finis et de mots infinis: |
| du semi-anneau de Boole au semi-anneau tropical. | ||
| 15h30 | Bruno Gaujal | Réseaux de Petri Fluides et Discrets |
| 16h30 | Pause | |
| 16h50 | Éric Menguy | Commande en boucle fermee dans l'algebre (max, +) |
| 17h50 | Fin de réunion |
| 9h30 | Serguei Samborski | Un nouveau type d'espaces fonctionnels |
| defini par des problemes extremaux | ||
| 11h00 | Pause | |
| 11h20 | Jean-Jacques | Sur la commande de graphes d'evenements |
| Loiseau | ||
| 14h30 | Albert Benveniste | Automates MaxPlus, dioïdes MaxMin associés, |
| applications à l'informatique temps-réel et distribuée | ||
| 16h00 | Pause | |
| 16h20 | Jean Mairesse | Semi-anneau (max,+), tas de pieces et reseaux de Petri |
| 17h20 | Fin de réunion |
| 9h30 | Bruno Gaujal | Multimodularité, convexité et propriétés d'optimisation |
| 11h00 | Pause | |
| 11h30 | Guy Cohen | Projecteurs max-plus linéaires |
| 12h30 | Déjeuner | |
| 14h30 | Stéphane Gaubert | Algorithmes de Howard dans l'algèbre max-plus |
| 16h00 | Pause | |
| 16h30 | Dohy Hong | Analytic expansions of (max,+) Lyapunov exponents |
| 17h15 | Alain Jean-Marie | Présentation d'ERS |
| 18h00 | Fin de la | |
| journée |
| 9h00 | Jacques | Automates a multiplicite dans (min, +) et le probleme de |
| Sakarovitch | l'etoile: une introduction. | |
| 10h30 | Pause | |
| 11h00 | Edouard Wagneur | Elements de geometrie et d'algebre max-lineaire |
| 14h00 | Jean-Eric Pin | Calcul de semigroupes |
| 15h00 | Michael Mc | Implementation of the max plus algebra in SCILAB |
| Gettrick | ||
| 16h00 | Fin de réunion |
| 9h30 | Christian Choffrut | Fonctions de mots realisees par automate fini |
| 11h00 | Pause | |
| 11h30 | Stéphane Gaubert | Asymptotique de la valeur propre de Perron |
| 12h30 | Déjeuner | |
| 14h30 | Bernard Derrida | Quelques problèmes de la physique statistique |
| des systèmes désordonnés et du non équilibre | ||
| 16h00 | Pause | |
| 16h30 | Bertrand | Synthèse de Feedbacks pour les GET dans les Dioïdes |
| Cottenceau | ||
| 17h30 | Table Ronde | Prochaines réunion, vie du groupe. |
| 18h00 | Fin de la journée |
| 9h00 | Paul Gastin | Séries rationnelles et séries reconnaissables |
| en variables partiellement commutatives. | ||
| 10h30 | Pause | |
| 10h45 | Ines Klimann | Un nouveau type d'automates pour la recherche de |
| sous-langages (A,B)-invariants maximaux | ||
| 12h15 | Déjeuner | |
| 14h00 | Jean-Paul Comet | Automates (max,+) et Alignements de séquences biologiques |
| 15h15 | Jean Assan | Calcul des sous-modules cles de l'approche geometrique |
| pour les systemes a coefficients sur un anneau. | ||
| 16h45 | Fin de réunion |
Algèbres Tropicales-ALAPEDES
| 9h30 | Claude Dellacherie | Théorie du potentiel élémentaire non linéaire |
| 11h30 | Gérard Duchamp | Un critère de rationalité provenant de la |
| géométrie non-commutative | ||
| 12h30 | Déjeuner | |
14h30 |
Christian Commault | Commande des systèmes structurés: |
| approche graphique. | ||
| 16h00 | Pause | |
16h30 |
Stéphane Gaubert et | Un bilan de trois ans d'activité |
| Jean-Jacques Loiseau | tropicale | |
| 18h00 | Table Ronde | (discussion ouverte) |
| 19h00 | Cocktail |
| 9h00 | Thomas Bonald | Effet du trafic transverse sur les performances |
| de TCP | ||
| 10h00 | Marc Artzrouni | Distances projectives, coefficients d'ergodicite, |
| et processus iteratifs lineaires et | ||
| "pseudo-lineaires" dans le cone positif de Rn | ||
| 11h00 | Pause | |
| 11h30 | Vassili Kolokoltsov | Deterministic approach to option pricing theory |
| 12h30 | Déjeuner |
| 14h00 | Alain Jean-Marie | New bounds for Lyapounov exponents of stochastic |
| (max,+) matrices | ||
| 14h25 | Bruno Gaujal | Analysis of preemptive periodic real time systems |
| 14h50 | Robert-Jan van Egmond | Railway capacity assessment, an algebraic approach |
| 15h15 | Jacob van der Woude | Conditions for the structural existence of an |
| eigenvalue of a bipartite (min,max,+)-system | ||
| 15h40 | Jean-Pierre Quadrat | Max-Plus objects in Scilab and application to |
| evaluation and optimisation of production systems. | ||
| 16h00 | Break | |
| 16h20 | Stefan Haar | Choosing a Semantics for Petri Nets |
16h45 |
Sabrina Mantaci | Tree codes and the defect theorems for trees |
| 17h10 | James Martin | Fast Jackson Networks |
| 9h00 | Natacha Portier | The minimal realization problem |
| in max-plus algebra is NP-hard | ||
9h25 |
Sam Lifsches | Hybrid Systems and Monadic Logic |
9h50 |
Eleni Katirtzoglou | Existence of the cycle time of DAD maps |
10h15 |
Bernd Heidergott | The Maclaurin Series for (Max,+) |
| Lyapunov Exponents: The Bernoulli Case |
Programmation Dynamique et Systèmes à ÉvÉnements Discrets
| 9h00 | Accueil des | |
| participants | ||
| 10h00 | J.P. Quadrat | Semiring, probability and dynamic programming |
| 10h30 | Quadrat/Gaubert | |
| 11h00 | S. Gaubert | From max-plus spectral theory to non-linear |
| Perron-Frobenius theory | ||
| 11h30 | Pause café | |
| 12h00 | F. Baccelli | Asymptotic Stationary Tail for Discrete |
| Déjeuner | Event Networks | |
| 12h30 | A. Hordijk | On the Optimality Equations of MDP's |
| 13h00 | Déjeuner | |
| 14h30 | K. Avrachenkov | Asymptotic simplex method and MDP's |
| 15h00 | J.P. Aubin | Two person dynamical games with a trapping |
| basin | ||
| 15h30 | M. Quincampoix | Existence of value of differential games |
| with state constraints | ||
| 16h00 | H. Frankowska | Semicontinuous solutions of Hamilton- |
| Jacobi-Bellman equations with state constraints | ||
| 16h30 | Pause café | |
| 17h00 | E. Altman | Constrained Markov Decision Processes |
| 17h30 | B. Gaujal | Monotonicity of feedback control with |
| multimodularity |
| 9h00 | S. Sorin | Zero-sum stochastic games: an introduction (I) |
| 9h30 | S. Sorin | Zero-sum stochastic games: an introduction (II) |
| 10h00 | Pause café | |
| 10h30 | D. Rosenberg | An operator approach to zero-sum repeated games |
| 11h00 | R. Laraki | Repeated games with lack of information on one side |
| 11h30 | N. Vieille | Non zero-sum stochastic games |
| 12h00 | Déjeuner | |
| 14h00 | P. Bernhard | Max-plus algebra and mathematical fear |
| 14h30 | J.B. Lasserre | Sample-path average optimality for Markov |
| control processes | ||
| 15h00 | F. Karaesmen | Optimal Control of Make-to-Stock Queues |
| 15h30 | F. Spieskma | Non-existence of the Puiseux expansion... |
| 16h00 | Pause café | |
| 16h30 | R. Elazouzi | Perturbation of Differential Games With Hybrid |
| Controls | ||
| 17h00 | T. Jimenez | Optimal Admission Control for High Speed |
| Networks |
Journée Systèmes Linéaires Positifs
| 9h30 | Georges Hansel | Séries rationnelles positives et probabilités |
| 10h45 | Pause | |
| 11h15 | Lorenzo Farina Nonnegative realizations | |
| 12h15 | Déjeuner | |
| 14h30 | Jean-Claude | L'Approche par Invariance Positive |
| Hennet | en Commande de Systèmes Dynamiques | |
| 15h45 | Pause | |
| Vers l'analyse de problèmes transitoires | ||
| 16h15 | Laurent Truffet | sur de grands modèles Markoviens |
| 17h15 | Fin de la journée |
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 ratropical00d.
The translation was initiated by on 2001-01-09