NoOrdre : 597ED 363UNIVERSIT DANGERSISTIACOLE DOCTORALE DANGERS2004Thse de DOCTORATSpcialit : Automatique et Informatique AppliquePrsente et soutenue publiquement parMehdi LHOMMEAUle 16 dcembre 2003 lISTIA - Universit dAngerstude de systmes vnements discretsdans lalgbre (max, +).1. Synthse de correcteurs robustes dans undiode dintervalles.2. Synthsedecorrecteursenprsencedeperturbations.JuryPrsident : Jean-Claude Gentina, Professeur cole Centrale de LilleRapporteurs : Guy Cohen, Professeur cole Nationale des Ponts et ChaussesJean-Jacques Loiseau, Directeur de Recherche CNRS, IRCCyN, NantesExaminateurs : Christian Commault, Professeur Institut National Polytechnique de GrenobleJean-Louis Ferrier, Professeur Universit dAngersLaurent Hardouin, Matre de Confrences Universit dAngersDirecteurs de thse : Jean-Louis Ferrier - Laurent HardouinLaboratoire : LABORATOIREDINGNIERIEDES SYSTMES AUTOMATISS. 62, avenue Notre Damedu Lac, F-49000 ANGERSTUDE DE SYSTMES VNEMENTS DISCRETS DANSLALGBRE (max, +).SYNTHSE DE CORRECTEURS ROBUSTES DANS UNDIODE DINTERVALLES.SYNTHSE DE CORRECTEURS EN PRSENCE DEPERTURBATIONS.Mehdi LHOMMEAU

Universit dAngersMehdi LHOMMEAUtude de systmes vnements discrets dans lalgbre (max, +). Synthse de cor-recteurs robustes dans un diode dintervalles. Synthse de correcteurs en prsencede perturbations.xxii+Cedocument atprparavecLATEX2et laclassethese-IRINversion0.92delas-sociationdejeunes chercheurs eninformatiqueLOGIN, UniversitdeNantes. Laclassethese-IRIN est disponible ladresse :http://www.sciences.univ-nantes.fr/info/Login/RsumLessystmesdynamiquesvnementsdiscretsmettantenjeudesphnomnesdesynchronisationpeuvent tre modliss par des quations linaires dans les algbres de type (max,+). Cette proprita motiv llaboration de ce que lon appelle communment la thorie des systmes linaires dans lesdiodes. Cette thorie prsente de nombreuses analogies avec la thorie conventionnelle des systmeslinaires continus et permet notamment daborder des problmes de commandes.La premire contribution concerne lanalyse de la robustesse de lois de commandes pour des systmes(max,+)-linaires.Lobjectifestdecaractriserlensembledessystmesprservantlesperformancesrecherches lors de la synthse. Autrement dit, nous cherchons caractriser les marges de variations oudrives du systme admissibles vis vis des critres de performances imposs.Ensuite, le problme de commande robuste est considr. Cette fois nous supposons connue, sous formedintervalles, lamplitude de variation des paramtres du systme commander et nous cherchons len-semble des correcteurs permettant datteindre un objectif donn. Au pralable est introduit un diodedintervalles, qui permet de modliser les systmes incertains sous forme de matrices dintervalles in-cluant lensemble des comportements possibles du systme. La synthse de contrleurs prsente dansle cas dterministe stend alors naturellement au contexte incertain.La dernire partie de ce mmoire traite du problme de commande en prsence de perturbations. Ense conformant la littrature sur les systmes continus conventionnels, nous montrons que ce problmeprsente de fortes analogies avec le problme classique du rejet de perturbations. Il est notamment montrquil est possible de synthtiser des contrleurs optimaux prservant ltat du systme dans le noyau dela matrice de sortie.Mots-cls : graphes dvnements temporiss, diodes, robustesse, commande en prsence de perturba-tions, algbre (max,+), analyse par intervallesAbstractDiscrete event dynamic systems involving synchronization phenomena can be modelled by linear equa-tions in some dioids. This property justied the development of what one commonly calls linear systemtheory in dioids. This theory presents many analogies with the classical linear system theory and allowsto tackle control problems.The rst contribution concerns the robustness analysis of control laws for (max,+)-linear systems. Theobjective is to characterize the set of systems preserving the desired performances at the time of thesynthesis. In other words, we try to characterize the acceptable variation margins or drifts for the systemwith respect to the imposed performances criteria.Then, the robust control problem is addressed. This time we suppose known, in the form of intervals,the amplitude of parameter variations of the system to be control and we seek the controller set allowingto achieve a given objective. As a preliminary a dioid of intervals is introduced, it makes possible tomodel the uncertain systems in the form of interval matrices including the set of all possible systembehaviors. Thecontrollersynthesispresentedinthedeterministiccasespreadsthennaturallytotheuncertain context.The last part of this report, deals with the problem of control in the presence of disturbances. Followingthe literature on classical continuous systems, we show that this problem presents strong analogies withthe classical problem of disturbance decoupling. In particular it is shown that it is possible to synthesizeoptimal controllers preserving the system state trajectories in the kernel of the output matrix.Keywords: discrete event systems, dioid, robustness, control in presence of disturbances, interval anal-ysisRemerciementsAu moment o sachve lcriture de ce manuscrit, jaurais pass presque quatre annes au Labo-ratoire dIngnierie des Systmes Automatiss. Je remercie en premier lieu son directeur le ProfesseurJ.-L. Ferrier de my avoir accueilli. Je tiens galement lui exprimer ma profonde gratitude pour sesconseils et son aide qui ont permis deffectuer cette thse dans les meilleures conditions possible.Jexprime toute ma reconnaissance G. Cohen, Professeur lcole Nationale des Ponts et Chaus-ses, et J.-J. Loiseau, Directeur de recherche CNRS lIRCCyN, pour lhonneur quils mont fait enacceptant de rapporter ce travail. Je leur suis galement trs reconnaissant pour les nombreuses remarqueset suggestions quils ont apportes.Je voudrais galement remercier C. Commault, Professeur lInstitut National Polytechnique deGrenoble, et J.-C. Gentina, Professeur lcole Centrale de Lille, de lintrt quils ont port cestravaux en acceptant de participer au jury.Je ne remercierai jamais assez L. Hardouin qui ma initi la recherche et a dirig cette thse. Sansses conseils, sa disponibilit et ses nombreuses suggestions, ce travail naurait jamais abouti. Je voudraisquil trouve ici lexpression de ma reconnaissance la plus sincre.Mes remerciements sadressent galement tous les membres du laboratoire, qui durant toutes cesannes mon permis de travailler dans un contexte agrable. Merci tous mes collgues doctorants.Jadresse mes remerciements ma mre ainsi qu toute ma famille et amis qui, de prs comme deloin mont aid et encourag au moment opportun.Enn et surtout, mille fois merci CarolineA ma mreA la mmoire de ma grand-mre qui na pas vu laboutissement de ce travailSommaireNotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiIntroduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii1 Outils algbriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Comportement linaire des GET dans les diodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 Commande et analyse de la robustesse de systmes (max, +)-linaires . . . . . . . . . . . . . . . . . . . . . 654 Synthse de contrleurs robustes pour les GET. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815 Commande de systmes (max, +)-linaires en prsence de perturbations . . . . . . . . . . . . . . . . . 103Table des matires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135A MinMaxGD : librairie de Calcul dans le diode /axin[[, ]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151ixNotationsZmax : diode (Z , + , max, +), appel aussi algbre (max, +).Zmin : diode (Z , + , min, +), appel aussi algbre (min, +).Zmax[[]] : diode des sries formelles en exposants dans Z et coefcients dans Zmax.Zmin[[]] : diode des sries formelles en exposants dans Z et coefcients dans Zmin.B[[, ]] : diode des sries formelles en et exposants dans Z et coefcients boolens./axin[[, ]] : quotient du diode B[[, ]] par la relation dquivalence :A, B B[[, ]] , A B_1_A = _1_B/ax+in[[, ]] : diode des lment causaux de /axin[[, ]]Im : image de lapplication : o T , Im = (s) [ s o.|A : restriction de lapplication au domaine A.B| : restriction de lapplication au codomaine B (avec Im B).B||A : restriction de lapplication au domaine A et au codomaine B (avec (A) B).

: application rsidue de lapplication : o T ,

(t) = s o [ (s) _ t.La : produit gauche par a, La(x) = a x.Ra : produit droite par a, Ra(x) = x a./ : application toile de Kleene dnie sur un diode complet, (s) = s =

i0si.T : application "plus" drive de ltoile de Kleene, T(s) = s+= s s =

i1si.ab : notation utilise pour reprsenter L

a(b).b/a : notation utilise pour reprsenter R

a(b).IU : injection canonique dun sous-ensemble U de o, IU: U oPrU : application rsidue de linjection canonique, PrU: o U.C(T) : diode de couples, issu dun produit direct de diodes.CO(T) : sous-diode de C(T) constitu des couples ordonns de C(T).I(T) : diode dintervalles.o(T) : ensemble des idaux principaux dun diode T.1(A, /) : ensemble des idaux principaux A-invariants inclus dans un idal principal /.1 : plus grand idal principal A-invariant inclus dans un idal principal /.1 : plus grand idal principal (ABF)-invariant inclus dans un idal principal /.1 : plus grand idal principal (ABFC)-invariant inclus dans un idal principal /.xiIntroductionLa thorie des systmes dynamiques vnements discrets1sintresse lanalyse et la conduitede systmes qui sont souvent de conception humaine. On peut par exemple citer les systmes de pro-duction (ateliers exibles, lignes dassemblage) [Cohen et al., 1983, Cohen et al., 1985], les rseaux decommunication (rseaux informatiques) [Le Boudec and Thiran, 2001] et les systmes de transport (rou-tier, ferroviaire ou arien) [Lotito et al., 2001, Houssin, 2003].De faon informelle, les systmes vnements discrets peuvent tre dnis comme des systmesdans lesquels les variables dtat changent sous loccurrence dvnements. Ils ne peuvent gnralementpas tre dcrits, linstar des systmes continus classiques, par des quations diffrentielles en raison dela nature des phnomnes qui entrent en jeu, notamment des phnomnes de synchronisation ou dex-clusion mutuelle. Ces systmes sont alors souvent reprsents par des modles tats-transitions. Les plusconnus sont les automates dtats nis qui servent pour reprsenter les systmes dterministes les plussimples, les chanes de Markov pour leur analogues stochastiques et les rseaux de Petri pour des sys-tmes plus complexes qui comportent la fois des phnomnes de synchronisation, de concurrence et deparalllisme.Le travail prsent dans ce mmoire porte sur lapproche communment appele thorie des systmeslinaires dans les diodes. Cette thorie, qui a vu le jour au dbut des annes 80, concerne essentiellementles systmes dynamiques vnements discrets qui mettent en jeu des phnomnes de synchronisation.Plus prcisment, il a t mis en vidence que cette classe de systmes admet une reprsentation linaire condition quelle soit dcrite dans une structure algbrique particulire appele diode. Depuis lintro-duction de cette thorie, de gros efforts ont t entrepris an de transposer, ou dadapter, les concepts etrsultats de la thorie conventionnelle des systmes linaires dans cette structure. Sans tre exhaustif, ilest possible de lister certains des rsultats existants :Lesproblmesdereprsentation(rponseimpulsionnelle,descriptiondanslespacedtat)ontt abords. On trouve galement, lapproche matrice (ou fonction) de transfert, introduite parlintermdiaire de transformes comparables la transforme en z de la thorie des systmes entemps discret [Cohen et al., 1984].Des mthodes danalyse spectrale ont galement t dveloppes. Ces mthodes danalyse four-nissent des lments dvaluation de performance du systme vnements discrets modlis.Les concepts de stabilit interne, de contrlabilit structurelle, ainsi que dobservabilit structu-relle, ont t dnis [Cohen et al., 1983, Cohen et al., 1991].Une vritable approche gomtrique pour ces systmes galement t introduite[Cohen et al., 1996,Cohen et al., 1997].Onconnatlefcacitdecesmthodesenthoriedessystmes linaires classiques.Certainsproblmesdecommandeontputrersoluspourcessystmes. Onpeutmentionnerla commande en juste--temps [Cohen et al., 1989]. Plus rcemment, la commande avec modle1Onpourragalementutiliserletermesystmesvnementsdiscrets, engardantlespritquilsagitdunsystmedynamique.xiiixiv Introductionde rfrence [Cottenceau et al., 2001],[Lders and Santos-Mendes, 2002],[Maia et al., 2003] et lacommande adaptative [Menguy et al., 2000] ont galement t tudies.Le travail prsent dans ce mmoire se situe dans la continuit de ces travaux. Plusieurs problmes decommande sont abords. Tout dabord, il sagit dtudier la robustesse dun systme pour lequel une loide commande optimale en boucle ouverte ou en boucle ferme a t synthtise. Plus prcisment, celava consister caractriser lensemble des valeurs que peut prendre le systme sans pour autant remettreen cause le caractre optimal de la loi commande. Nous abordons galement le problme de synthsede correcteurs pour des systmes incertains, cest--dire des systmes dont les paramtres ne sont pasconnus avec exactitude. Enn, on sintresse la traduction dans les diodes dun problme trs clas-sique de la thorie des systmes, le problme du contrle en prsence de perturbations.Ce mmoire est structur en cinq chapitres comme suit :Dans le premier chapitre nous prsentons les outils algbriques ncessaires la reprsentation et la commande des graphes dvnements temporiss. Nous donnons tout dabord des rsultatsgnraux sur les structures ordonnes et treillis. Nous mentionnons galement le concept didalet de ltre dans un ensemble ordonn. Ces rsultats jouent un rle cl dans le chapitre cinq sur lacommande en prsence de perturbations. Une part importante de ce premier chapitre est ensuiteconsacre la thorie de la rsiduation. En particulier il est mis en vidence que certaines appli-cations non rsiduables peuvent bncier de restrictions rsiduables. Nous donnons galementquelques lments sur les correspondances de Galois ; celles-ci permettent de revisiter certains r-sultats de la thorie de la rsiduation. La dernire partie de ce chapitre est entirement ddie laprsentation des diodes et de leurs liens avec les structures ordonnes prsentes dans la premirepartie.Le second chapitre prsente la modlisation des graphes dvnements temporiss sur diffrentsdiodes rencontrs dans la littrature. Nous insistons particulirement sur la prsentation du diode/axin[[, ]], qui sera le diode considr pour toutes les illustrations prsentes dans ce mmoire.Lavantage de cette structure concerne le transfert entre-sortie dun GET qui se prsente alorssous forme dune matrice rationnelle. Ds lors, ltude des GET est lie lalgbre des sriesrationnelles de /axin[[, ]]. Ce chapitre doit tre considr comme une synthse bibliographique.Dans le troisime chapitre, nous tudions la synthse et la robustesse de lois de commande enboucle ouverte et en boucle ferme pour les systmes (max, +)-linaires. Nous dsirons en parti-culier dterminer des marges de variations "admissibles" pour le systme command. Nous enten-dons par marges admissibles, les rgions dans lesquelles le systme peut varier sans remettre encause loptimalit de la commande. Pour la boucle ouverte, ltude de la robustesse repose sur unrsultat dmontr laide des correspondances de Galois, nous caractrisons alors le plus grandsystme admettant la mme commande optimale que le systme nominal. Pour la boucle ferme,ltude de la robustesse, quant elle, dcoule dun rsultat sur la rsiduation de fermetures.Dans le quatrime chapitre, nous examinons le problme de synthse de contrleurs robustes vis--vis des incertitudes paramtriques du systme. Dans un premier temps, nous introduisons undiode dintervalles, ce diode permettra par la suite de modliser le comportement dun systme(max, +)-linaire quali dincertain. Dans le cas de GET, ces incertitudes se traduisent par lefait que le nombre de jetons ou la dure des temporisations ne sont pas connus avec prcision,on connat seulement leurs amplitudes maximales de variation, par consquent nous supposeronsquils appartiennent des intervalles. Ensuite, nous montrons en particulier que lapplication pro-duit dnie sur le diode dintervalles est rsiduable. Cest en partie sur ce rsultat que repose laIntroduction xvsynthse de contrleurs robustes. Enn, nous utilisons ces rsultats dans un exemple o lobjectifest de caractriser lensemble des correcteurs stabilisant un graphe dvnements temporis.Dans lecinquimechapitre, nous nous intressons auproblmedecommandedesystmes(max, +)-linaires en prsence de perturbations. Dans le cas de GET, ces perturbations ont poureffet de retarder le franchissement des transitions internes et par consquent de ralentir le fonc-tionnementglobaldusystme. Notreobjectifestdeprendreencomptecesinformationsdansllaboration de la commande. Pour cela, nous introduisons tout dabord la notion didaux prin-cipaux invariants. Ensuite, nous montrons que pour certains idaux principaux invariants il existeune commande en boucle ferme permettant de conserver ltat du systme lintrieur de ceux-ci. Ces proprits, nous permettent alors de donner lexpression de plusieurs correcteurs de typeretour dtat et de type retour de sortie. Ce chapitre se termine par une illustration reprsentant unatelier de production dans lequel lobjectif est de synthtiser un correcteur permettant de diminuerles stocks internes du systme dans le cas o une perturbation survient.Une annexe prsente les scripts Scilab qui ont permis de calculer les exemples proposs tout aulong du mmoire. Il sagit de scripts utilisant la bote outils Lminmaxgd dveloppe en C++au laboratoire. Une partie des travaux de thse a t consacre au dveloppement de cette bote outils.CHAPITRE 1Outils algbriques1.1 IntroductionCe chapitre prsente les outils algbriques utiliss dans le cadre de ce mmoire. Sans tre exhaustifs,nous proposons une prsentation sufsamment dtaille permettant au lecteur non initi dapprhenderefcacement lasuitedecerapport. Lesouvragesayant servi sardactionsont [Birkhoff, 1940],[Dubreil and Dubreil-Jacotin, 1964], [Blyth and Janowitz, 1972], [Cuninghame-Green, 1979],[Baccelli et al., 1992], [Gaubert, 1992]. Ce chapitre est construit de la faon suivante.Dans les sections 1.2, 1.3 et 1.4 sont prsents un ensemble de dnitions, de notations et de rsultatsrelatifs aux structures ordonnes et aux treillis. Nous rappelons notamment des rsultats gnraux sur lesidaux et les ltres dune structure ordonne ainsi que sur les applications isotones et les morphismes detreillis [Dubreil and Dubreil-Jacotin, 1964],[Birkhoff, 1940].Aprs avoir prsent les treillis, nous dtaillons dans la section 1.5 la thorie de la rsiduation. Cettethorie concerne des applications croissantes dnies sur des ensembles ordonns et permet sous deshypothses de continuit de caractriser la plus grande solution de linquation (x) _b ou la pluspetite solution de linquation (x) _ b [Blyth and Janowitz, 1972].Tout dabord nous rappelons les principales proprits des applications rsiduables. Nous prsentonsensuite les restrictions dapplication, ce qui nous permet daborder ltude dapplications "partiellementrsiduables", cest--dire pour lesquelles une plus grande solution existe si le domaine ou le codomainesont restreints un sous-ensemble. En particulier, il apparat dans la partie 1.6 que la restriction dunefermeture son image est une application rsiduable [Blyth and Janowitz, 1972, Cottenceau, 1999].La thorie des correspondances de Galois permet de revisiter certains rsultats de la thorie de larsiduation, lorsque les applications tudies sont dcroissantes. Aprs avoir rappel la dnition et lesproprits des correspondances de Galois, nous montrons dans la partie 1.8.1 que la notion de corres-pondancedeGaloisetlanotiondapplicationrsiduableconcident,unrenversementdordreprs[Blyth and Janowitz, 1972, Akian et al., 2002].Le paragraphe suivant est consacr ltude des diodes. Le but de cette partie est de faire le lienentre ces structures algbriques et les rsultats sur les ensembles ordonns. Nous rappelons notammentquun diode est dot dune structure de treillis et que la thorie de la rsiduation sapplique naturellement[Cohen et al., 1989, Baccelli et al., 1992, Cohen, 1998a].Depuisquelquesanneslquipe(max, +) delINRIAadveloppuneapprochegomtriquecomparable lapproche dveloppe dans [Wonham, 1985, Basile and Marro, 1992]. Lapproche go-mtriqueest notamment connueenthoriedessystmespourapporterunregarddiffrent surcer-tains problmes de commande.Les paragraphes 1.12 et 1.13 noncent certains des rsultats obtenus[Cohen et al., 1996, Cohen et al., 1997, Cohen et al., 1998b].12 CHAPITRE1 Outils algbriques1.2 Structures ordonnes et treillisCette section prsente les points cls de la thorie des treillis. Les treillis sont des concepts math-matiques que lon peut manipuler en tant quensembles ordonns ou en tant que structures algbriques.Les treillis ont t amplement tudis dans la littrature, nous renvoyons le lecteur [Birkhoff, 1940]et [Dubreil-Jacotin et al., 1953] pour cette partie. Des rappels sur la thorie des treillis sont galementdonns dans [Baccelli et al., 1992] et [Blyth and Janowitz, 1972].1.2.1 Structures ordonnesDnition 1.1 (Ensemble ordonn). Unensembleordonnestunensemble omunidunerelationdordre, cest--dire une relation binaire qui est rexive, antisymtrique et transitive. Cette relation seranote _ et un ensemble ordonn sera not (o, _).Un ensemble est dit totalement ordonn si deux lments quelconques s et s

sont toujours compa-rables, cest--dire si lon a s _ s

ou s

_ s.La notation s s

signie s _ s

et s ,= s

.Remarque 1.2. En prsence dambiguts sur lensemble considr, nous dsignerons par la notation_S lordre dun ensemble o.Tout sous-ensemble U dun ensemble ordonn (o, _) peut galement tre ordonn par la restrictionde lordre de o aux lments de U, note _U. Cet ordre restreint est simplement dni paru, u

U o, u _ u

u _Uu

.Remarque 1.3. Si (o, _) est partiellement ordonn, un sous-ensemble U o, ordonn par la restrictionde _ U, peut tre tel que tous les lments de U soient incomparables deux deux. Lensemble (U, _)est alors dit totalement non ordonn.Un ensemble ordonn ni (o, _) peut tre reprsent par un graphe appel diagramme de Hasse.Chaque lment de oest reprsent par un sommet (). Un arc reliant deux sommets du diagrammesigniequeleslmentsreprsentsparcessommetssontcomparables. Parconvention, lordreestcroissant dans le sens du bas vers le haut du diagramme._6t

t @@@tta bcd a et b sont incomparablesa _ c, b _ c, c _ da _ d, b _ d (par transitivit de lordre _)Figure 1.1 Diagramme de Hasse dun ensemble ordonn (a, b, c, d, _)Pour la gure 1.1, lensemble o = a, b, c, d est partiellement ordonn pour lordre _ dcrit par lediagramme. Le sous-ensemble U= a, b oest un ensemble ordonn par la restriction de _ U.Nanmoins, dans ce cas prcis, (U, _) est totalement non ordonn (remarque 1.3).CHAPITRE1 Outils algbriques 3Remarque 1.4. Un ensemble totalement ordonn est galement appel une chane en rfrence sondiagramme de Hasse qui en est une.Exemple 1.5 (Ensembles ordonns).(R, ), (Z, ), (N, ), (Q, ) o est lordre naturel, sont totalement ordonns.Soit o un ensemble. Lensemble des parties de o, not T(o), est un ensemble ordonn par linclusion.Cet ensemble ordonn est not (T(o), ). Il sagit dun ordre partiel. Par exemple, deux sous-ensembles disjoints de o ne sont pas comparables suivant lordre .Soit (o, _) un ensemble ordonn. Lensemble des vecteurs__de o21est ordonn par lordre____ab_( _ a et _ b).Mme si _ est total sur o, lordre quil induit sur o21nest que partiel.Remarque 1.6. On dira que deux ensembles ordonns sont isomorphes si leurs diagrammes de Hasseont la mme forme.Dnition 1.7 (Majorant, minorant). Soit o un ensemble muni dune relation dordre _ et U un sous-ensemble de o.On appelle minorant de U tout lment s de o tel que u U, s _ u.On appelle majorant de U tout lment s

de o tel que u U, u _ s

.Dnition 1.8 (Bornes dun ensemble). Un sous-ensemble U o est dit born sil admet un majorantet un minorant. Lorsque lensemble des majorants de U a un plus petit lment, ce plus petit lment estappel borne suprieure de U. On le note sup(U) ou_U. De mme lorsque lensemble des minorantsde U a un plus grand lment, on lappelle borne infrieure de U (note inf(U) ou_U).Exemple 1.9. Soit lensemble o= a, c, d, e, f, g, h, j partiellement ordonn pour lordre _ dcritpar le diagramme de la gure 1.2. Soit le sous-ensembleU= a, d, h, j. Lensemble des majorantss

= f, j et lensemble des minorants s = c, d, g de U sont hachurs. Remarquons que sup(U) = jet inf(U) = d. Notons quun minorant (resp. majorant) de U nappartient pas forcment U.Remarque 1.10 (lments particuliers dans un ensemble ordonn). Dans un ensemble ordonn o,on appelle plus petit lment, un lment Stel que lon ait S _s pour tout s o. Notons quun tellment, sil existe, est ncessairement unique, car sil y en avait deux, Set

S, on aurait S _

Set

S _ S, donc S =

S.De mme, on appelle plus grand lment, un lment Stel que lon ait s _ Spour tout s o.Notons galement quun tel lment, sil existe, est ncessairement unique.1.2.2 Demi-treillis et treillisDnition 1.11 (Demi-treillis). Un sup-demi-treillis est un ensemble o ordonn, dans lequel tout coupledlments (s, s

) admet une borne suprieure (plus petit majorant) note sup(s, s

) ou s s

. De mme,un inf-demi-treillis est un ensemble oordonn, dans lequel tout couple dlments (s, s

) admet uneborne infrieure note inf(s, s

) ou s s

.4 CHAPITRE1 Outils algbriquesFigure 1.2 Reprsentation de lensemble des majorants (resp. minorants) du sous-ensemble U oRemarque 1.12 (Principe de dualit). Notons _oplinverse de la relation dordre _. Si (o, _) estun sup-demi-treillis, alors (o, _op) est un inf-demi-treillis, et vice versa. Par consquent, une relationimpliquant _, et reste vraie en remplaant _ par _op et en permutant et . Il sagit du principede dualit.Dnition 1.13 (Treillis). Un treillis est un ensemble ordonn (o, _) qui est la fois un sup-demi-treillis et un inf-demi-treillis ; autrement dit, un treillis est un ensemble ordonn dans lequel tout coupledlments admet un plus petit majorant et un plus grand minorant.Exemple 1.14.(N, _div), o lordre sur N est dni para _divba divise b, (1.1)est un treillis. Les lois de treillis de (N, _div) sont a b = ppcm(a, b) et a b = pgcd(a, b).Dnition 1.15 (Sous-treillis). On appelle sous-treillis dun treillis o, un sous-ensembleUde oqui,avec chaque couple u, u

de U contient aussi uu

et uu

dans U. On dit aussi que ce sous-ensembleest ferm pour les lois et .Remarque 1.16. Il faut noter quun sous-ensemble U peut tre un treillis sans tre un sous-treillis de o.Exemple 1.17. Considrons le diagramme de Hasse dun treillis ni ocontenant 8 lments (gure1.3). On remarque que les ensembles h, d, e, b, h, d, f, a sont des sous-treillis, il en est de mmepour lensemble h, f, c, g qui en outre est une chane.Par contre, lensemble h, d, e, a nest pas un sous-treillis, car d e (c.--d. b) ne fait pas partie delensemble.Nanmoins on voit que h, d, e, a est un treillis (pour la relation dordre existant entre a, d, e et hdans o) mais pas un sous-treillis de o puisque dans a, d, e, h, d e = a alors que, dans o, d e = b.CHAPITRE1 Outils algbriques 5ss s sss sshd e fba cg

@@@@@@@@@@@@@@@@@@@@

Figure 1.3 Diagramme de Hasse du Treillis (o, _)Dnition 1.18 (Demi-treillis complet et treillis complet). Un sup-demi-treillis (resp. inf-demi-treillis)o est dit sup-complet (resp. inf-complet) si tout sous-ensemble (ni ou inni) de o admet un plus petitmajorant (resp. un plus grand minorant) dans o. Un treillis est dit complet sil est la fois inf-complet etsup-complet.Remarque 1.19. Pour un sup-demi-treillis complet not (o, ), la borne sup de tout sous-ensemble deoest dnie, y compris pour o. Un sup-demi-treillis complet oa donc ncessairement un plus grandlment not S =_sS s . Pour la mme raison, un inf-demi-treillis complet (o, ) a toujours un pluspetit lment not S= _sS s. En outre, un demi-treillis ni est complet (sup-complet ou inf-complet)et un treillis ni est complet.Exemple 1.20.En ajoutant llment + Z, lensemble (Z +, ) est totalement ordonn sup-complet.En revanche, (Q +, ) est un ensemble totalement ordonn qui nest ni sup-complet ni inf-complet. Par exemple, le sous-ensemble x Q[ x 2 de Q na pas de plus petit majorantdans Q.Thorme 1.21. Un sup-demi treillis complet oest un treillis complet si, et seulement si, il a un pluspetit lment S.Dmonstration.() si o est un treillis complet alors il admet un plus petit lment S(cf. dnition 1.18 et remarque1.19).() supposons que oest un sup-demi-treillis complet et possde un plus petit lment S. SoitU=uA un sous-ensemble non vide de o, etM= mBlensemble des minorants deU.Lensemble M est non vide puisque S M. Posons m =_B m ; llment mest dni danso puisque o est complet.Par dnition de lensemble M,u U, m M, m _ u,6 CHAPITRE1 Outils algbriquesou encore,u U, m =

Bm _ u.DoncmestminorantdeU, etparconsquent, leplusgranddesminorantsdeU. Toutsous-ensemble non vide de oadmettant un plus grand minorant, oest un inf-demi-treillis complet etdonc galement un treillis complet.Remarque 1.22. En raison du principe de dualit nonc dans la remarque 1.12, on peut noncer ledual du thorme prcdent : un inf-demi-treillis complet est un treillis complet si, et seulement si, il aun plus grand lment S.Remarque 1.23. Les dnitions prcdentes de demi-treillis et treillis ont t introduites de faon en-sembliste, elles font uniquement intervenir les proprits de la relation dordre _ dnie sur lensemble.Il est intressant de faire le lien entre ce point de vue ensembliste et le point du vue algbrique.En algbre, un treillis est parfois dni comme un ensemble muni de deux oprations binaires et jouissant des proprits classiques dassociativit, de commutativit et didempotence, et de la propritdite dabsorption : x (x y) =x =x (x y). Dans ce cas, la notion dordre peut tre drive ;x _ y est par dnition x = x y (ou x y = y).Cest l une des principales raisons de limportance de la notion de treillis : elle permet de rem-placer la relation x _y par des quations x y=y x y=x, et par consquent de traiter lesquestions relatives lordre par des moyens algbriques : des oprations, des quations. De plus, il estdsormais possible de remplacer lexpression "soit o un treillis" par (o, _) ou par (o, , ).1.3 Idaux et ltres1.3.1 IdauxDnition 1.24 (Idaux dans un ensemble ordonn). Soit oun ensemble ordonn. On appelle idal("lower set" en anglais) de o toute partie non vide I de o satisfaisant(x I et y _ x) y I.De mme un idal principal ("closed lower set" en anglais) (gnr par x) de o est un idal de la forme :[, x] = y o [ y _ x.1.3.2 FiltresDnition 1.25 (Filtres dans un ensemble ordonn). Soit oun ensemble ordonn. On appelle ltre("upper set" en anglais) de o toute partie non vide Fde o satisfaisant(x Fet y _ x) y F.De mme un ltre principal ("closed upper set" en anglais) (gnr par x) de o est un idal de la forme :[x, ] = y o [ y _ x.CHAPITRE1 Outils algbriques 7Exemple 1.26. On considre lensemble ordonn de la gure 1.4. Les ensembles c et a, b, c, d, esont des idaux. Dautre part, a, b, d, f et a, b, c, e sont des idaux principaux, lun gnr par fet lautre par e. Par contre, lensemble b, d, e nest pas un idal. Dautre part, d, f, g est un ltreprincipal gnr par d. Par contre a, b, d, f est un simple ltre.Figure 1.4 Idaux et Filtres dans un ensemble ordonn.1.3.3 Cas dun treillisDans un treillis, on considre la fois la notion didal et de ltre. Dans un treillis, tout idal principal(resp. tout ltre principal) est un sous-treillis.Exemple 1.27. On considre le sous-ensemble ni de (N, _div), dni par1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. Cet ensemble correspond lensemble des diviseurs de 60.On considre alors le treillis suivant :Figure 1.5 Treillis des diviseurs de 60.Dans ce treillis, nous avons reprsent :- Lidal principal gnr par llment 6, cest--dire [, 6] = 1, 2, 3, 6 (en tirets). On remarqueque [, 6] est ferm pour et .8 CHAPITRE1 Outils algbriques- Le ltre principal gnr par llment 6, cest--dire [6, ] = 6, 12, 30, 60 (en pointills). Demme que pour lidal, le ltre [6, ] est ferm pour et .1.4 Isotonie, morphismes et continuit1.4.1 IsotonieDnition 1.28 (Isotone, antitone, monotone). Soit : o T une application dnie sur des en-sembles ordonns. On dira : isotone s, s

os _ s

(s) _ (s

), antitone s, s

os _ s

(s) _ (s

), monotone isotone ou antitone.1.4.2 MorphismesDnition 1.29 (Morphismes). Soient (o, _) et (T , _) deux treillis et une application de o dans T .Alors est un -morphisme si(s s

) = (s) (s

)pour tout s, s

o.De faon analogue, est un -morphisme si(s s

) = (s) (s

)pour tout s, s

o.Si est la fois un -morphisme et un -morphisme, alors est un morphisme de treillis.Figure 1.6 Morphisme entre les treillis o et T .Remarque 1.30. Un -morphisme (resp. un -morphisme) est une application isotone. En effet, pourun -morphisme par exemple : si s _ s

, alors ss

= s

, donc (ss

) = (s) (s

) = (s

), doCHAPITRE1 Outils algbriques 9(s) _ (s

). Par contre la rciproque est fausse, une application isotone nest pas ncessairement un ou -morphisme. Cependant, si : o o est isotone, on aura toujours(s s

) _ (s) (s

) s, s

o,puisques s

_ s (s s

) _ (s)s s

_ s

(s s

) _ (s

)_(s s

) _ (s) (s

).De mme, pour un -morphisme(s s

) _ (s) (s

) , s, s

o.Exemple 1.31. Considrons lapplication isotone : (N, _div) (N, _) , x x. Alors, soient leslments 4 et 6 dans (N, _div), le vaut 4 6 = 12, alors que le des lments 4 et 6 dans (N, _)vaut 6. Par consquent on a, (4 6) = 12 ,= (4) (6) = 6. Cependant, on remarque que lon abien (4 6) _ (4) (6).Dnition 1.32 (Image dune application).Limage de : o Test le sous-ensemble de Tconstitupar les lments de Tde la forme (s) o s o ; limage de se note (o) ou Im.1.4.3 ContinuitDnition 1.33 (Continuit). Soit une application dun treillis complet o dans un treillis complet T ,lapplication est semi-continue infrieurement (s.c.i. en abrg), respectivement semi-continue sup-rieurement (s.c.s.) si, pour toute partie U o, on a_ _uUu_=_uU(u), (1.2)respectivement,_ _uUu_=_uU(u). (1.3)Remarque 1.34. Toute fonction semi-continue infrieurement (respectivement semi-continue suprieu-rement) est un -morphisme (respectivement un -morphisme). Alors daprs la remarque 1.30, toutefonction semi-continue infrieurement (respectivement semi-continue suprieurement) est isotone.Remarque 1.35. Si est une fonction isotone mais non semi-continue infrieurement, on ne peut pluscrire __uU u_=_uU (u), mais on a toujours __uU u___uU (u). En effet, __uU u_est un majorant de lensemble (U), en raison de lisotonie de , tandis que, par dnition, _(U)est le plus petit majorant de ce mme ensemble.1.5 Thorie de la rsiduationDans cette partie nous allons introduire la thorie de la rsiduation, dont une rfrence essentielle est[Blyth and Janowitz, 1972]. La rfrence [Cohen, 1998a] en propose galement une synthse. Soit :o Tune application dnie sur des ensembles ordonns. On sintresse la rsolution dquationsdu type(s) = t, t T . (1.4)10 CHAPITRE1 Outils algbriquesCetteapplicationpeuttrenonsurjective(problmedelexistence)et/ounoninjective(problmede lunicit). La thorie de la rsiduation permet de donner une rponse ce problme de rsolutiondquation, en dterminant la plus grande sous-solution de lquation (1.4) (cest--dire la plus grandesolution de (s) _ t).Le lecteur trouvera galement dans [Cuninghame-Green, 1979, 10], [Baccelli et al., 1992, 4.4.2],[Gaubert, 1992] et [Cottenceau, 1999, 1.2] des rappels dtaills sur cette thorie.1.5.1 Applications rsiduablesDnition 1.36 (Applications rsiduables). Une application isotone : o T dnie sur des en-sembles ordonns est dite rsiduable, si lquation (s) _ t admet une plus grande solution dans o pourtout t T . On notera

lapplication rsidue, avec

(t) =_s o [ (s) _ t.Remarque 1.37. La thorie de la rsiduation permet aussi de considrer des quations du type (s) _ t.Dans ce cas, on dit que lapplication est dualement rsiduable si elle admet une plus petite solutiondans o pour tout t T , lapplication rsidue est alors note

. Nous naborderons pas ltude de cesapplications dans la suite du manuscrit, le lecteur intress pourra consulter [Blyth and Janowitz, 1972]et [Cohen, 1998a].Le thorme suivant fournit une caractrisation de ces applications.Thorme 1.38. Soit : o T une application isotone dnie sur des ensembles ordonns. Sontquivalents1. lapplication est rsiduable ;2. il existe une application

: (T , _) (o, _) isotone telle que

_ IdT(identit de T ) (1.5)

_ IdS(identit de o). (1.6)Dmonstration.1 2Lapplication rsiduable implique que

(t)= _s o [ (s) _ t existe pour tout t T .Par hypothse, est isotone ; on alors _

(t)__ t, c.--d. ,

_ IdT.Dautre part, par la dnition 1.36, on a

((s

)) = _s o [ (s) _(s

) et commes

s o [ (s) _ (s

), on a_s o [ (s) _ (s

) _ s

, cest--dire

_ IdS.Il reste montrer que

est isotone ; soit t

_ t, alors

(t

) _ t

_ t

(t

) s o [ (s) _ t.En dautres termes,

(t

) est solution de (s) _ t, ce qui implique

(t

) _ _s o [ (s) _t =

(t). Donc pour rsumer, t

_t

(t

) _

(t), cest--dire que lapplication

estisotone.2 1Soit

telle que

(t) _ t pour tout t T , alors s =

(t) est toujours solution de (s) _ t.De plus, pour toute solution s

o vriant (s

) _t, on a

((s

)) _

(t) puisque

estisotone, cest--dire daprs (1.6),s

_

(s

) _

(t). Toute solutions

de (s) _t, etce pour tout t T , est plus petite que

(t). Donc llment

(t) est la plus grande solution delquation (s) _ t pour t T , ou encore est rsiduable.CHAPITRE1 Outils algbriques 11Proprits 1.39 (Unicit de

). Lorsque : o Test rsiduable, lapplication

est unique. Eneffet supposons quil existe une autre application vriant le point 2 du thorme 1.38. On remarqueque

= IdS

_ ( )

= (

) _ IdT= , = IdS _ (

) =

( ) _

IdT=

.Par consquent on a

= .Le thorme suivant fournit des rsultats de la thorie de la rsiduation auxquels il sera frquemmentfait rfrence par la suite.Thorme 1.40. Soit : o Tet : T deux applications rsiduables. =

et

=

(1.7)( )

=

(1.8) est injective

= IdS

est surjective (1.9) est surjective

= IdT

est injective (1.10)Dmonstration.(1.7) Lapplication tant rsiduable, la relation (1.6) permet dcrire

= _

__ .Inversement, la relation (1.5) donne

=_

_ _ .Ceci conduit au rsultat =

. La dmonstration de

=

est similaire ense rappelant que

est isotone.(1.8) Soient et deux applications rsiduables, alors daprs (1.6) et (1.5), dune part

= (

)

_ IdT

=

_ IdW,et dautre part,

=

(

) _

IdT =

_ IdS.En outre, daprs la proprit 1.39, si lapplication ()

existe, elle est unique ; par consquent,( )

=

.(1.9) (

= IdS

est surjective) s o,

(s)=s implique o=Im

, c.--d.

estsurjective.(

= IdS

est surjective) Inversement, si

est surjective, pour tout s o, il existet Ttel que

(t) = s, donc

(s) =

(t) =

(t) = s (application de (1.7)).(

= IdS est injective) (s) = (s

) s =

(s) =

(s

) =s

, donc est injective.(

= IdS est injective) Si est injective, pour tout s o lgalit suivante (

(s)) = (s) implique

(s) = s.12 CHAPITRE1 Outils algbriques(1.10) Preuve semblable (1.9).Remarque 1.41. Il faut noter que si lapplication est rsiduable, et si (s) =t admet une solution,alors (s) = t admet

(t) comme plus grande solution.Le thorme qui suit donne une condition ncessaire et sufsante dexistence de lapplication

lorsque lapplication est dnie sur des treillis complets.Thorme 1.42. Soit : o Tune application isotone dnie sur des treillis complets o et Tde pluspetits lments respectifs S et T. Lapplication isotone : o Test rsiduable si et seulement si est semi-continue infrieurement (s.c.i) et (S) = T.Dmonstration. Si est rsiduable, lensemble s o [ (s) _T admet un plus grand lment s

et par isotonie de , (S) _ (s

) _ T. Comme, dautre part, (S) _ T, on a (S) = T.Montrons ensuite que est semi-continue infrieurement. Lapplication tant isotone, il apparatque pour tout U o :_ _uUu___uU(u). (1.11)Soit

lapplication rsidue de . La relation (1.6) donne u _

(u), alors_ _uUu__ _ _uU

(u)_.De mme lisotonie de

entrane_ _uU

(u)__

_ _uU(u)_.Par ailleurs, la relation (1.5) donne

_ _uU(u)___uU(u).Finalement, pour rsumer, on obtient_

uUu__ _

uU

(u)__

_

uU(u)__

uU(u),soit linverse de la relation (1.11), ce qui prouve que est semi-continue infrieurement.Rciproquement, si (S) = T, pour tout t T , lensemble U= s o [ (s) _ t est non vide.De plus, tant semi-continue infrieurement, __uU u_=_uU (u), donc U o admet un plusgrand lment.CHAPITRE1 Outils algbriques 131.6 Restrictions dapplicationsNous rappelons dans cette partie des rsultats noncs dans [Blyth and Janowitz, 1972] et certainsdans [Cohen, 1998a] et [Cottenceau, 1999, 1.2.2]. Par restriction dune application on entend la restric-tion de son domaine et/ou de son codomaine de dnition. Les restrictions dapplications vont permettredtudier des cas o la proprit de rsiduabilit est conserve aprs restriction, ou linverse, des cas ola restriction dune application non rsiduable devient rsiduable.Dnition 1.43 (Injection canonique dun sous-ensemble). SoitUun sous-ensemble de lensembleo. Linjection canonique de Udans oest lapplication IU: U o, dnie par IU(u) =u pour toutu U.Dnition 1.44 (Application image). Lapplication image de : o Test linjection canonique de(o) dans T; cette application sera note IIm.Dnition 1.45 (Restriction dune application un domaine).Soit : o Tet U un sous-ensemblede o. Nous noterons |U: U Tlapplication vriant|U= IUo IU: U o reprsente linjection canonique de U dans o. Lapplication |U sera appele restrictionde au domaine U.Dnition 1.46 (Restriction dune application un codomaine). Soit : o Tet Im V T .Nous noteronsV | : o Vlapplication dnie par lgalit = (IV ) _V |_o IV: V Treprsente linjection canonique de Vdans T . LapplicationV | sera dite restriction de au codomaine V .Dnition 1.47 (Restriction double). Soit : o T ,U oet (U) V T . Nous noteronsV ||U: U Vlapplication dnie par lgalit|U= IU= (IV ) _V ||U_.La proposition suivante concerne la rsiduation de linjection canonique.Proposition 1.48 (Lemme de projection [Blyth and Janowitz, 1972, Gaubert, 1992]). Soient ountreillis complet (cf. dnition 1.18) et U un sous-treillis complet de o contenant le plus petit lment Sde o. Linjection canonique IU: U o est rsiduable. Lapplication rsidue PrU= I

U vrie :(i) PrU PrU= PrU(ii) PrU _ IdS(iii) u UPrU(u) = u.Dmonstration. Vrions dabord que IUest une application rsiduable. Dune part, comme S U,on a IU(S) =S. Dautre part, Utant un sous-treillis complet, on a IU_ _xXx_ = _xXIU(x), pourtout X U. Par consquent linjection canonique IU: U o est rsiduable (cf. thorme 1.42).14 CHAPITRE1 Outils algbriques(i) I

U I

U= (IU IU)

= I

U (par (1.8))(ii) PrU= IU PrU= IU I

U _ IdS(iii) siu U, alors u=IU(u), donc PrU(u)=PrU IU(u)=I

U IU(u) _u. En outre daprs(ii), PrU(u) =IU PrU(u) =IU I

U(u) _u, do u U PrU(u) =u. La rciproque estimmdiate.1.6.1 Rsiduation contrainteComme nous lavons vu (1.5) la thorie de la rsiduation permet de caractriser si une application dnie sur des ensembles ordonns admet une unique application jouant le rle dapplication inverse.Si lapplication est dnie sur des treillis complets, il a t montr que lexistence tait assure pour peuque lapplication soit semi-continue infrieure.Dans cette partie nous allons nous intresser la rsiduation contrainte introduite par [Cohen, 1998a,1.3]. Le problme de rsiduation contrainte consiste rechercher une solution (s) _ b, b T , nonpas dans o tout entier, mais dans un sous treillis complet osub de o contenant le plus petit lment S deo.Remarque 1.49. SoitISsublinjection canonique de osub dans o. Rsoudre (s) _t avecs osubrevient considrer une quation du type|Ssub(t) = ISsub(s) _ t, (1.12)et rechercher la plus grande solution dans osub. Le diagramme suivant commute1:osub6o T-

3ISsub|SsubDaprs la proposition 1.48, on sait que linjection canonique dun sous-treillis dans un treillis estrsiduable, la proposition suivante donne un lment de rponse au problme de rsiduation contrainte.Proposition 1.50. Soient : o T une application rsiduable dnie sur des treillis complets etISsub linjection canonique du sous-treillis complet osub (contenant le plus petit lment Sde o) danso. Lquation ISsub(s) _ t est rsiduable et sa rsidue est donne par_|Ssub_

(t) = ( ISsub)

(t) = PrSsub

(t).(1.13)Dmonstration. Daprs (1.8), on a_|Ssub_

= ( ISsub)

=I

Ssub

. De plus par application dulemme de projection (cf. proposition 1.48), I

Ssubexiste et est note PrSsub, do le rsultat (1.13).Proposition 1.51. Soient : o Tune application rsiduable dnie sur des treillis complets et ITsublinjection canonique du sous-treillis complet Tsub (avec Im Tsub T ) dans T . LapplicationTsub|est rsiduable et_Tsub|_

=

ITsub =_

_|Tsub.1un tel diagramme est dit commutatif lorsque les diffrentes applications permettant daller dun point un autre sont gales.CHAPITRE1 Outils algbriques 15Dmonstration. Si est rsiduable, alors pour tout t T ,

(t) est la plus grande solution de (s) _ t.En particulier, pour tout t Tsub T , il existe une plus grande solution (s) _ t. LapplicationTsub|est donc, par dnition, rsiduable. Sa rsidue_Tsub|_

est simplement la restriction de

au domaineTsub, note_

_Tsub.1.7 FermeturesNous tudions ici une classe particulire dapplications isotones : les fermetures.Dnition 1.52 (Fermeture). On appelle fermeture une application : (o, _) (o, _), qui a lesproprits suivantes :elle est extensive : _ IdSelle est idempotente : = elle est isotone : s, s

o, s _ s

(s) _ (s

)Dans ces conditions, limage (s) dun lment s o sappelle -fermeture de s, et si llment sest gal sa -fermeture, on dit que s est -ferm.Notons que si lensemble o possde un lment maximum, celui-ci est -ferm ; en effet, il rsultedu fait que lapplication est extensive que _ () _ .Exemple 1.53. Lapplication a : o o, x a x est une fermeture ; en effet on aa a(x) = a (a x) = a x = (x) _ x,cest--dire a a = a _ IdS.Lemme 1.54. Si : (o, _) (o, _) et : (o, _) (o, _) sont des fermetures et des -morphismes,alors est aussi une fermeture.Dmonstration. Comme_IdSet _IdS, ona _IdS. Deplus, ettantdes -morphismes, on a( ) ( ) = ( ) ( ) = .Dautre part, comme et sont idempotentes, on a = .Mais comme, _ IdS _ et _ IdS _ , on peut donc crire = ,ce qui prouve que est une fermeture.Notation 1.55. Soit : o oune fermeture dnie sur un treillis o. On notera Im limage de ,cest--direIm = (s) [ s o .16 CHAPITRE1 Outils algbriquesProposition 1.56. Limage de : o o, soit Im, correspond lensemble des -ferms de o.Dmonstration. Par dnition (s) est un ferm et dautre part tout lment s ferm est limage par dau moins s lui-mme, puisque (s) = s.Proposition 1.57. Soient une fermeture dun treillis complet o et R une partie de Im. Si la partie Ra une borne infrieure, celle-ci appartient encore Im.Dmonstration. Soit Rune partie de o constitue dlments de Im pour laquelle u = _rRr existe. Pardnition de la borne infrieure, pour tout lment r de R, r _ u, et, puisque est isotone, (r) _ (u).De plus, comme tout lment de Im est -ferm, on a r= (r). Il sensuit que (r) =r _ (u),cest--dire que (u) est un minorant de R et donc que (u) _ _rRr = u. Toutefois, tant extensive,(u) _ u. Finalement, on a (u) = u, donc la borne infrieure de Rappartient bien limage de .Proposition 1.58. Soit une fermeture dun treillis complet o. Limage de est, elle aussi, un treilliscomplet (not (Im,Im,Im )) pour lordre de o ; de plus, pour toute partie R de Im,Im_rRr = _rRr ,Im_rRr = _ _rRr_. (1.14)Dmonstration. SoitR une partie deIm. Daprs la proposition 1.57, _rRr Im, par consquent_rRr =Im_rRr, cest--dire que Im est un inf-demi-treillis complet. En outre, on sait que le plus grandlment de o est ferm. Ainsi, daprs le thorme 1.21 et la remarque 1.22, Im est un treillis complet.Il reste prouver la formule relative aux bornes suprieures. On pose u = _ _rRr_. Lapplication tant extensive, on a u = _ _rRr__ _rRr ; autrement dit, u est un majorant de Rdans o. En outre,u Im; par consquent u est un majorant de R dans Im. Alors, soit y _ _rRr, et, puisque estcroissante, (y) _ _ _rRr_ = u. Si, en particulier, y Im, on voit que (y) = y _ u. On prouveainsi que u est effectivement le plus petit majorant de R dans Im.Remarque 1.59. La proposition prcdente montre que limage dune fermeture , soit Im, dans untreillis complet o est stable pour lopration , cest--dire (s) (s

) Im, et que lopration nest dordinaire pas ferme, cest--dire que (s)(s

) nappartient pas Im. Par consquent Imnest donc pas un sous-treillis de o. Nanmoins, on peut munir Im dune structure de treillis, ce treillis(Im,Im,Im ) est dni pars1, s2 Im___s1Im s2= (s1 s2)s1Im s2= s1 s2.Ce treillis (Im,Im,Im ) admet , le plus grand lment de o, pour majorant universel, et (S) =Im, lment minimum de Im dans o, pour minorant universel. Schmatiquement, les lments de oet Im peuvent tre reprsents par la gure 1.7.CHAPITRE1 Outils algbriques 17Figure 1.7 lments du treillis o et lments de Im.Proposition 1.60. SoitIm| lapplication dnie du treillis (o, , ) dans le treillis (Im,Im,Im ),alorsIm| est un -morphisme, cest--direIm|(s s

) =Im| (s) Im| (s

) , s, s

o.Dmonstration. Pour tout couple s, s

o, lapplication tant extensive, on a (s) _ s et (s

) _ s

,do(s) (s

) _ s s

.Dautre part, par dnition deImet par isotonie de on a(s)Im (s

) = ((s) (s

)) _ (s s

) _ (s) (s

) (cf. remarque 1.30).Par ailleurs, lapplication tant idempotente, on a 2= ; on obtient alors(s s

) = 2(s s

) = ((s s

)) _ ((s) (s

)) = (s)Im (s

).Donc, (s s

) = (s)Im (s

), par consquentIm| est un -morphisme.1.7.1 Fermeture et rsiduationProposition 1.61. Soit : (o, _) (o, _) une fermeture dnie sur un treillis complet o. La restric-tionIm| est rsiduable et sa rsidue_Im|_

= IImest linjection canonique IIm de Im dans o.18 CHAPITRE1 Outils algbriquesDmonstration. Daprs le thorme 1.38Im| est rsiduable si et seulement si il existe une application

telle queIm|

_IdIm et

Im| _IdS. En posant

=IIm, oIIm est linjectioncanonique de Im dans o, on vrie queIm| IIm =Im| |Im = IdIm (identit de Im) puisque = (dnition 1.52) ; de mme, daprs la dnition 1.46, on a IImIm| = _ IdS.Proposition 1.62. Une fermeture rsiduable : (o, _) (o, _) vrie :(i) =

(ii) =

.Dmonstration.(i) Lapplication tant rsiduable, le point (ii) du thorme 1.38 donne

_IdS, ce quiimplique

_IdS =; tant une fermeture, on a

=

, soit

_ . Dautre part, tant rsiduable, on a (daprs (1.7)) =

; de plus, daprsla dnition dune fermeture _ IdS, nous avons donc =

_ IdS

=

,soit _

. Finalement, on a =

.(ii) Preuve duale de (i).1.8 Correspondances de GaloisLes applications rsiduables sont parfois appeles correspondances de Galois. Dans la suite, nousallons considrer les correspondances de Galois au sens de [Ore, 1944] (voir dnition 1.63). Nous ver-rons que les applications rsiduables/rsidues et les correspondances de Galois sont quivalentes selonune dualit dordre. Nous expliquerons cette dualit la n du paragraphe.Dnition 1.63 (Correspondance de Galois). Soient (o, _) et (T , _) deux treillis complets et deuxapplications : o Tet : T o. On dit que le couple (, ) dapplications tablit une corres-pondance de Galois entre o et Tsi les quatre conditions suivantes sont satisfaites :(i) s, s

o, s _ s

(s) _ (s

) ( est antitone)(ii) t, t

T , t _ t

(t) _ (t

) ( est antitone)(iii) pour tout lment s de o, s _ (s)(iv) pour tout lment t de T , t _ (t)Remarque 1.64. Il est important de noter que le rsultat de la composition dapplications antitones estisotone ; en effet, daprs la dnition dune application antitone, on as _s

(s) _(s

) ((s)) _ ((s

)).Proposition 1.65. Soient : o T et : T odeux applications dnies sur des treillis com-plets. tablir que le couple (, ) est une correspondance de Galois (dnition 1.63) entre o et Testquivalent avoir la condition suivantes o, t T s _ (t) t _ (s), (1.15)ou plus explicitement,(t) = _s o [ (s) _ tet(s) = _t T [ (t) _ s .CHAPITRE1 Outils algbriques 19Dmonstration. On suppose que le couple (, ) forme une correspondance de Galois, et soit t _ (s).Alors en appliquant successivement les points (ii) et (iii) de la dnition 1.63, nous obtenonst _ (s) =(t) _ ((s)) = (s) _ s,do le rsultat t _ (s) (t) _ s.Maintenant, si s _ (t), daprs (i) et (iv) de la dnition 1.63, on as _ (t) (s) _ ((t)) = (t) _ t.Par consquent, si (, ) est une correspondance de Galois, on a bien le rsultat s o, t T , s _(t)t _ (s).Rciproquement, on suppose que lon a s _ (t) t _ (s). Pour tout s o nous pouvonscrire (s) _ (s) ; alors, par hypothse :(s) _ (s)s _ ((s)) = (s),on vrie donc bien le point (iii) de la dnition 1.63. Soits, s

oavecs _s

, daprs (iii) on as

_ (s

), cest--dires _ s

_ (s

) = ((s

)).Alors daprs notre hypothse en prenant t = (s

), on as _ s

_ ((s

))(s

) _ (s),ce qui implique s _s

(s

) _ (s). On obtient ainsi le point (i) de la dnition. Pour les points(ii) et (iv) la preuve est similaire.Proposition 1.66. Soit (, ) un couple dapplications tablissant une correspondance de Galois entredeux treillis complets o et T , alors pour tout U o_ _uUu_= _uU(u) et _ _uUu_= _uU(u).Dmonstration. On a,t _ _

uUu_(t) _

uUu (u U, (t) _ u) (u U, t _ (u)) t _

uU(u),pour tout U S, t T . La preuve est similaire pour lautre galit.Thorme 1.67 ([Ore, 1944]). Soit (, ) un couple dapplications tablissant une correspondance deGalois entre des ensembles ordonns o et T . Alors : o o et : T Tsont des fermetures.Dmonstration. Il rsulte de la dnition dune correspondance de Galois que est extensive (c.--d. _IdS) et isotone ( tant la composition de deux applications antitones). Il reste montrerquelle est idempotente. Or daprs la dnition 1.63, pour tout lment s de o, (s) = ( ) (s) _ (s). (1.16)Mais (s) T , et ainsi, daprs la dnition 1.63, (s) _ ((s)) = (s). Il rsulte delantitonie de que (s) _ (s). (1.17)(1.16) et (1.17) conduisent = ( ) ( ) = . En changeant les rles de et , on voit que est aussi une fermeture.20 CHAPITRE1 Outils algbriquesProposition 1.68. Soient : o Tet : T o deux applications dnies sur des treillis complets.Si le couple (, ) tablit une correspondance de Galois, alors on a = (1.18) = (1.19)Dmonstration. Si (, ) tablit une correspondance de Galois, alors le point (iv) de la dnition 1.63donne t _ (t) pour tout t T . On pose t = (s), on obtient alors (s) _ (s). Dautrepart, daprs le point (iii) de la dnition dune correspondance de Galois, on a s _ (s) et comme est une application antitone (point (i) de 1.63), on a (s) _ (s), do lgalit = .Pour (1.19), la preuve est duale de (1.18).1.8.1 Lien entre correspondance de Galois et rsiduationComme de nombreux auteurs [Blyth and Janowitz, 1972, Picado, , Gaubert, 1992] le mentionnent,les applications rsidues et les correspondances de Galois sont quivalentes selon une dualit dordre.Dnition 1.69. Si (o, _S) est un ensemble ordonn, on note par (oop, _Sop ) lensemble ordonn op-pos, pour lequel s _Sop s

s _Ss

.Proposition 1.70. Soit : o Topune application rsiduable dnie sur des treillis complets. Alorsle couple (,

) tablit une correspondance de Galois entre o et T .Dmonstration. Si est une application rsiduable alors daprs le thorme 1.38, les applications :o Topet

: Topo sont isotones, cest--dire antitones sur o, T . Par ailleurs, la relation (1.6) duthorme 1.38 donne(s) _Top (s)

(s) _S

(s) s _S

(s).De mme, daprs (1.5), on a

(t) _S

(t)

(t) _Top

(t)

(t) _Top t

(t) _Ttpour touts o, t T . Alors le couple dapplications (,

) tablit une correspondance de Galoisentre o et Tpuisque

(s) _Ss et

(t) _Tt.Remarque 1.71. La proposition prcdente prcise le lien entre les applications rsiduables/rsiduesetlescorrespondancesdeGalois. Eneffet, uncouple (, )decorrespondancesdeGaloisentre(o, _) et (T , _) correspond un couple dapplications telles que est une application rsiduable de odans Top, et une application rsidue de Topdans o.Remarque 1.72. Comme il est soulign dans [Blyth and Janowitz, 1972] il est souvent prfrable duti-liser la thorie de la rsiduation plutt que les correspondances de Galois. La raison principale vientdu fait que la composition dapplications rsiduables donne une nouvelle application rsiduable, ce quinest pas le cas pour des applications antitones. En effet, si : o T et : T sont desapplications rsiduables, alors est clairement rsiduable, puisque ( )

=

(1.8).CHAPITRE1 Outils algbriques 211.9 Monodes et diodes : approche combinatoireCette section est un rappel sur les structures algbriques considres. Le but de ce paragraphe est din-troduire les concepts et notations qui seront utiles pour ltude de la commande de graphes dvnementstemporiss. Les ouvrages de rfrence qui ont inspir cette synthse sont [Cuninghame-Green, 1979],[Baccelli et al., 1992]et [Gunawardena, 1998]ainsi quelesthses[Moller, 1988],[Gaubert, 1992]et[Cottenceau, 1999].Dnition 1.73 (Monode). Unmonodeestunensemble cmuniduneloidecompositioninterneassociative, et dun lment neutre pour cette loi. Nous noterons la loi additivementc c c(a, b) a bet llment neutre sera not . Le monode est dit commutatifsi lon aa b = b apour tous les lments a, b c.Remarque 1.74. Unlment acest idempotent si a a =a. Si tousleslmentsde csontidempotents, le monode (c, ) est dit idempotent.Exemple 1.75. Lensembledesentiersnaturels Nmunideladditionestunmonode.Ilsagitdunmonode commutatif : a, b N, a +b = b +a. Llment neutre de N est 0.Dnition 1.76 (Demi-anneau, diode). On appelle demi-anneau un ensemble Tmuni de deux loisinternes et tel que :(T, ) est un monode commutatif dont llment neutre est appel lment nul.(T, ) est un monode. Son lment neutre est appel unit et est not e.La loi multiplicative est distributive droite et gauche par rapport la loi additive .Llment neutre est absorbant pour la loi (a T, a = a = ).Si en outre la loi est idempotente (cf. remarque 1.74), alors (T, , ) est quali de demi-anneauidempotent ou diode.Exemple 1.77 (Algbres (max,+) et (min,+)). On peut vrier aisment que :(R , max, +) est un diode commutatif pour lequel= ete=0. Ce diode est notRmax et est traditionnellement appel "algbre (max, +)".Rmin=(R +, min, +)estundiodecommutatif, appel"algbre(min, +)", pourlequel = +et e = 0.1.9.1 Sous-diodeDnition 1.78 (Sous-diode). Soit (T, , ) un diode. Un sous-ensemble c T est un sous-diodede (T, , ) si et seulement si : c et e c ; c est ferm pour les lois et .Le second point signie que a, b c, a b c et a b c.Exemple 1.79. Zmax = (Z, max, +) et Zmin = (Z+, min, +) sont respectivement dessous-diodes de Rmax et Rmin.22 CHAPITRE1 Outils algbriques1.9.2 Calcul matriciel dans les diodesExemple 1.80 (Diode matriciel). Soit (T, , )undiode,onnote Tnnlensembledesmatricescarres n lignes et n colonnes coefcients dans T. La somme et le produit de matrices sont dnisde faon classique par :(AB)ij = Aij Bijet (AB)ij =n

k=1Aik Bkji, j = 1 . . . , n, A, B Tnn.Lensemble Tnnmunidecesdeuxoprationsestundiode. Llmentneutrepourlaloi estlamatrice dont tous les coefcients valent , laquelle sera aussi note . Llment neutre pour la loi estla matrice dont tous les coefcients valent , sauf ceux de la diagonale qui valent e. Cette matrice seranote e, ou E lorsquil est utile de la distinguer du scalaire e.1.9.3 Sries formelles dans les diodesExemple 1.81. Soit (T, , ) un diode et fune application de Z dans T. On dnit la srie formelleF(z) en lindtermine z coefcients dans T par :F(z) = tZf(t)zt.Nous dsignerons par < F(z), zt> le coefcient f(t) de F(z) pour zt. Lensemble des sries formellesen lindtermine z et coefcients dans T muni des oprationsF(z) G(z) : < F(z) G(z), zt> = < F(z), zt> < G(z), zt>F(z) G(z) : < F(z) G(z), zt> =

i+j=t< F(z), zi> < G(z), zj>est un diode not T[[z]].Exemple 1.82 (Diode de polynmes). On appelle support dune srie formelle F(z) lensembleSupp(F(z)) = t Z [ f(t) ,= .Lorsque le support est ni on parle de polynme. Le sous-ensemble des polynmes muni des mmes loisque T[[z]] est un sous-diode de T[[z]] not T[z].1.10 Diodes et structures ordonnesLobjet de ce paragraphe est dtablir un lien entre les diodes prsents prcdemment de faonpurement combinatoire et la thorie des treillis. Ce lien entre diodes et treillis va permettre dnoncerdes rsultats obtenus en appliquant certains rsultats de la partie consacre aux treillis. Les ouvrages derfrence pour cette partie sont [Cuninghame-Green, 1979] et [Baccelli et al., 1992]CHAPITRE1 Outils algbriques 231.10.1 Diodes canoniquement ordonnsLidempotence delaloi additive permet dednir naturellementunerelation dordredansundiode. Le thorme suivant afrme de plus que cette relation dordre est compatible avec les lois dudiode.Thorme 1.83. Dans un diode (T, , ), la relation _ dnie para _ b a b = b (1.20)est une relation dordre. De plus cette relation dordre est compatible avec les lois de structure de T,cest--dire,a _ b a c _ b c c T,a _ b a c _ b c et c a _ c b c T.Dmonstration. Comme laddition est idempotente, on a a =a a _a, ce qui montre la rexivit.Laddition tant commutative, sia _b etb _a alorsb=a b=b a=a, doa=b, ce quiprouve lantisymtrie. Il reste montrer la transitivit : a _ b et b _ c alors c = b c = (a b) c =a (b c) = a c. On en dduit que _ est une relation dordre.Montrons que la relation dordre est compatible avec les lois et . Soit a, b T avec a _b et soitc T, on a b c = (a b) c = a b c = a c b c = (a c) (b c), do a c _ b c.De mme, b c = (a b) c = (a c) (b c), do a c _ b c (idem pour la multiplication gauche).La relation dordre est dite totale sia, b T, a _ b ou b _ a.Une condition ncessaire et sufsante pour que lordre dun diode soit total, scrit de faon videntea, b T, a b = b ou a.Cest--dire que lopration vrie la proprit dite de slectivit ; dans ce cas le monode (T, )et le diode (T, , ) sont dits slectifs ([Gondran and Minoux, 2001, 6.4]).Remarque 1.84. Lordre _ dni dans Rmax est total et concide avec lordre usuel . En revanche,lordre total _ dni dans Rmin est linverse de lordre usuel (par exemple 2 _ 1).1.10.2 Diodes et treillisDans cette partie nous prsentons les relations entre diodes, sup-demi-treillis et treillis. Le thorme1.83 de la partie prcdente permet dtablir que lidempotence de la somme dans un diode induit unestructure de sup-demi-treillis (dnition 1.11), pour lequel la borne suprieure, note , correspond laloi additive (a b est le plus petit majorant de a et b) du diode. De mme en considrant la remarque1.23 sur la dnition algbrique dun sup-demi-treillis, on peut noter que la loi dun sup-demi-treillisest associative, commutative et idempotente, cest--dire que possde les mmes axiomes que la loiadditive dun diode. De plus, on sait, daprs la dnition 1.76, quun diode possde un lmentminimum (plus petit que tous les autres lments du diode), ce qui confre au diode une structure detreillis (voir thorme 1.21).24 CHAPITRE1 Outils algbriques1.10.3 Diode completDnition 1.85 (Diode complet). Un diode (T, , ) est dit complet sil est ferm pour les sommesinnies et si la loi distribue ( gauche et droite) sur les sommes innies, cest--dire si pour toutb T et tout sous-ensemble A T,b _

aAa_= aA(b a) et_

aAa_b = aA(a b) .Il rsulte de cette dnition que, pour tout A T et B T :_

aAa__

bBb_=

(a,b)AB(a b) .Exemple 1.86. Le diode Zmax complt par llment +est un diode complet notZmax=(Z , +, max, +). De mme on note Rmax=(R , +, max, +) le diodeRmax complt par llment +.Puisqueundiode Taunestructuredetreillis(T, _), silestcomplet, iladmetunplusgrandlment. On notera ce plus grand lment. Llment correspond la somme de tous les lmentsde T = xDx.Cet lment est absorbant pour la loi additive a, a = , et vrie = = .Dnition 1.87 (Borne inf). Si T est un diode complet, alors est la loi associative commutative etidempotente vrianta b = x [ x _ a et x _ b ,et faisant de (T, , ) un treillis complet. Cette loi vrie en consquencea = a ba _ bb = a b. (1.21)Remarque 1.88.La relation (1.21) peut faire penser que les oprateurs et jouent un rle symtriquedans un diode. En considrant uniquement la structure de treillis dun diode cette assertion est vraie(en considrant le principe de dualit). Mais, elle devient fausse si lon considre la seconde oprationdun diode . Cependant, le produit droite (il en est de mme pour le produit gauche) tant uneopration isotone, on vrie la relation de sous-distributivit suivante :c (a b) _ (c a) (c b) a, b, c T.Lexemple qui suit (emprunt [Cohen, 2001, 2.3.1.3]) illustre cette proprit.Exemple 1.89. On considre le diode_2R2, , +_. Soienta = (1, 0), b = (0, 1) et c = [1, 1] [1, 1]on ac(a b) = c + (a b) = c + = ,(ca) (cb) = (c +a) (c +b)= ([0, 2] [1, 1]) ([1, 1] [0, 2])= [0, 1] [0, 1],donc (ca) (cb) _ c(a b).CHAPITRE1 Outils algbriques 251.10.4 Diode distributifDnition 1.90 (Diode distributif). Un diode (T, , ) est distributif sil est complet et si a T etpour tout sous-ensemble C de T, on a :_ _cCc_a =_cC(c a)et_

cCc_ a = cC(c a) .Remarque 1.91. Les lois et sont des lois de treillis, elles sont donc isotones pour lordre _. Si lediode nest pas distributif, on vrie nanmoins toujours les ingalits suivantes :a (b c) _ (a b) (a c)a (b c) _ (a b) (a c).1.10.5 Morphismes de diodesDnition 1.92 (Homomorphisme, isomorphisme).Une application : T c dnie sur des diodesest un homomorphisme sia, b T (a b) = (a) (b) et () = (1.22)(a b) = (a) (b) et (e) = e (1.23)Une application vriant seulement (1.22) est dite -morphisme, cest--dire que limage dune sommedlments de T est la somme, dans c, de leurs images. Une application vriant seulement (1.23) estdite -morphisme, cest--dire que limage dun produit dlments de T est le produit, dans c, de leursimages.Dnition 1.93 (Isomorphisme). Une application : T cdnie sur des diodes est un isomor-phisme, si

est dnie sur c et si et

sont des homomorphismes.1.10.6 Congruence et diode quotientDnition 1.94 (Congruence). Une congruence sur un diode T est une relation dquivalence (note1) compatible avec les lois du diode, cest--direa 1b (a c) 1(b c), (a c) 1(b c), a, b, c T.Thorme 1.95 (Diode Quotient). Soit un diode Tet 1 une congruence sur T. En notant [a] =x T[ x1a la classe dquivalence de a T, le diode quotient de T par cette congruence est undiode not T/R pour lequel la somme et le produit sont dnis par[a] [b]df= [a b][a] [b]df= [a b](1.24)26 CHAPITRE1 Outils algbriquesDmonstration. Il convient de souligner quen raison de la compatibilit de 1avec les lois du diode T,en prenant a, a

et b, b

tels que [a] = [a

] et [b] = [b

] on obtient[a b] = [a

b

] et [a b] = [a

b

],cest--dire que les classes [ab] et [ab] dpendent seulement des classes [a] et [b] et non des reprsen-tants de ces classes. Les oprations sur le quotient donnes par (1.24) sont par consquent parfaitementdnies et confrent au quotient T/R une structure de diode.Thorme 1.96. Soit un homomorphisme de T dans c. La relation 1 dnie para 1b (a) = (b), a, b T,est une congruence.Dmonstration. Le fait que 1est une relation dquivalence est immdiat. Dautre part, puisque est un homomorphisme, lensemble (T) est ferm pour les lois et de c. De plus, les lmentsneutres pour laddition et le produit de cappartiennent galement (T) ( est un homomorphismedonc () = et (e) =e). Donc, (T) bncie dune structure de diode. Lapplication T/R (T), [a] (a) dnit alors un isomorphisme de diodes.1.11 Thorie de la rsiduation applique aux diodesLes principaux rsultats prsents ici sont issus de [Baccelli et al., 1992] et [Gaubert, 1992]. Le lec-teur retrouvera galement la plupart des ces rsultats dans [Cohen, 1998a].1.11.1 Applications rsiduables sur les diodes completsOn se propose ici dtudier le caractre rsiduable de certaines applications de rfrence dnies surdes diodes complets.Thorme 1.97. Soient (T, , ) et (c, , ) deux diodes complets de plus petits lments respectifsD et C. Une application isotone : T c est rsiduable si et seulement si, pour tout ensemble X deT_

xXx_=

xX(x) (1.25)(D) = C. (1.26)Dmonstration. La preuve de ce thorme est identique celle du thorme 1.42 puisquil t montrprcdemment (voir 1.10) quun diode complet pouvait tre assimil un treillis complet.Soient La et Ra les applications suivantes dnies sur un diode complet TLa: x a x (1.27)Ra: x x a (1.28)En rfrence la dnition 1.85, sur un diode complet, la multiplication distribue sur les sommesinnies, gauche ou droite. De plus, La() = et Ra() =. En appliquant le thorme 1.97, La etRa sont donc rsiduables sur un diode complet.CHAPITRE1 Outils algbriques 27Lorsque T est commutatif, La = Ra implique donc galement L

a = R

a.Nous utiliserons les notations suivantes introduites notamment dans [Baccelli et al., 1992].Notation 1.98 (Applications Rsidues de La, Ra). Nous noteronsL

a(x) = a x =xaR

a(x) = x /a =xales applications rsidues respectives de La et Ra.Le tableau qui suit prsente un ensemble de proprits de ces applications dont le lecteur pourra trou-ver les preuves dans [Baccelli et al., 1992, p. 182-185],[Gaubert, 1992, 5.3], [Cottenceau, 1999, 1.3.3].a(ax) _ x (x/a)a _ x (f.1)a(ax) _ x (xa)/a _ x (f.2)a(a(ax)) = ax ((xa)/a)a = xa (f.3)a(x y) = ax ay (x y)/a = x/a y/a (f.4)(a b)x = ax bx x/(a b) = x/a x/b (f.5)(ab)x = b(ax) x/(ba) = (x/a)/b (f.6)b(ax) _ (a/b)x (x/a)b _ x/(ba) (f.7)(ax)b _ a(xb) b(x/a) _ (bx)/a (f.8)1.11.2 Fermetures rsiduables sur les diodes completsNotation 1.99 (Etoile de Kleene). Soit T un diode complet. Lapplication toile de Kleene, dnie surT, sera note / par la suite,/ : T Tx x = k0xk.On utilisera galement une notation particulire pour lapplication "plus" drive de ltoileT : T Tx x+= k1xk.Les applications / et Tsont isotones (par composition dapplications isotones) eta=e a+oua+=a a. De plus les applications / et T sont des fermetures ; en effet, a _a et (a) =a; demme a+_ a et (a+)+= a+.28 CHAPITRE1 Outils algbriquesRemarque 1.100. En accord avec les rsultats sur les fermetures dnies sur des treillis (1.7), il estpossible de munir Im/ et ImTdune structure de treillis. Nous noterons ces treillis (Im/,ImK,ImK ) et(ImT,ImP,ImP) en posantk, k

Im/___kImK k

= /(k k

) = (k k)kImK k

= k k

etp, p

ImT___pImP p

= T(p p

) = (p p

)+pImP p

= p p

.Remarque 1.101. Lapplication / : x x de T T nest pas rsiduable ; en effet, elle ne vrie pasla condition de semi-continuit infrieure du thorme 1.97. Pour illustrer cette remarque, considronsles matrices suivantesa =_ 11 _et b =_ 11 _alors(a b) =_ _,= ab =_e 11 e__e 11 e_=_e 11 e_on remarque que pour ces deux valeurs la condition de semi-continuit infrieure nest pas vrie. Celasignie que lquation /(x) =b na pas de solution b T. Malgr tout, il existe une restrictionrsiduable de lapplication /, la proposition suivante prcise cette notion.Proposition 1.102. Soit lapplication / : T T, x x dnie sur un diode complet. LapplicationImK|/ est rsiduable et sa rsidue est_ImK|/_

= IImK,o IImK est linjection canonique de Im/ dans T.Dmonstration. Il sagit dune application directe de la proposition 1.61.Remarque 1.103. On peut dduire de la proposition prcdente 1.102, que x =a est la plus grandesolution de linquation x _ a. En fait cette plus grande solution satisfait lgalit x = a.1.12 Noyaux, imagesLa plupart des rsultats ainsi que les notations nonces dans cette partie sont issus des rfrences[Cohen et al., 1996, Cohen et al., 1997, Cohen, 1998a].Nous rappelons tout dabord que limage dune application B : | A, est dnie parImB = B(u) [ u | .Dnition 1.104 (Noyau). Le noyau de lapplication linaire C: A , not ker C, est dni par larelation dquivalencexker C x

C(x) = C(x

).(1.29)Cette relation dnit une congruence (voir thorme 1.96). Lensemble quotient A/ ker Cest donc len-semble des classes dquivalence modulo ker C.CHAPITRE1 Outils algbriques 29Remarque 1.105. Le lemme 1.96 montre que la relation dquivalence (1.29) est une congruence.Notation 1.106. Une classe dquivalence de A/ ker C sera note [x]C.Proposition 1.107. SiC: A est une application rsiduable alors chaque classe dquivalence[x]C contient un et un seul lment de ImC

qui, de plus, est le plus grand lment dans cette classe.Dmonstration. Si C est rsiduable, daprs (1.7), C = CC

C, alors x A, C(x) = C_(C

C)(x)_.Autrement dit,xker C C

C(x).Considrons maintenant un lment x

[x]C, alors C(x

) = C(x) = CC

C(x) ; de plus le thorme1.38 donne C

C _ IdX ; par consquentx

_ C

C(x

) = (C

(C C

C))(x)= (C

C)(x) (par (1.7)).Donc, C

C(x) est plus grand lment de [x]C. Il reste montrer lunicit de cet lment. Si C

(y)ker CC

(y

), alors C(C

(y)) = C(C

(y

)) et C

C C

(y) = C

C C

(y

), soit C

(y) = C

(y

) daprs(1.7).Proposition 1.108. Si C: A est une application rsiduable alors la relation dquivalenceker Cvriex _ y _ zxker C z_xker C yker C z.Dmonstration. Dune part, commeCest rsiduable, elle est isotone ; par consquent, six _y _zalors C(x) _ C(y) _ C(z). Dautre part, xker C z entrane C(x) = C(z) ; donc C(x) = C(y) = C(z),do xker C yker C z.Remarque 1.109. Dans [Blyth and Janowitz, 1972], les auteurs qualient de convexes les classes dqui-valence vriant la proposition prcdente.Les deux propositions qui suivent sont nonces sans preuve, le lecteur intress pourra se reporter [Cohen et al., 1996, Cohen et al., 1997].Proposition 1.110. Soient les applicationsB: | Aet S: Q A, oSest une applicationrsiduable, alors sont quivalents :(i) ImB ImS ;(ii) B = S S

B;(iii) il existe une application L : | Q telle que B = S L.Proposition 1.111. Soient les applications C : A et F: A |, alors sont quivalents :(i) ker C ker F ;(ii) F= F C

C(iii) il existe une application H : | telle que F= H C.30 CHAPITRE1 Outils algbriques1.13 ProjecteursDans [Cohen et al., 1996, Cohen et al., 1997], les auteurs dnissent la notion de projection. Troistypes de projections sont introduites, les projections paralllement au noyau dune application, les pro-jections dans limage dune application et les projections dans limage dune application paralllementau noyau dune autre application.1.13.1 Projection paralllement au noyau dune applicationSoit lapplicationC: A , daprs la proposition 1.107 nous savons que pour toutx A, ilexiste un unique lment dans [x]CImC

. Cet lment est donn par C

C. Le lemme qui suit prciseles proprits de cet lment.Lemme 1.112 ([Cohen et al., 1996]). Soit C : A une application rsiduable. Alors C= C

Cvrie les proprits suivantes(i) Cest un projecteur, cest--dire C C= C;(ii) C C= C.(iii) C_ Id ;(iv) C(x) est le seul lment quivalent x modulo ker C appartenant ImC

;(v) C(x) est le plus grand lment dans la classe dquivalence [x]C;Dmonstration. les proprits (i), (ii) et (iii) dcoulent directement de (1.7) et (1.6). Les proprits (iv)et (v) sont donnes par la proposition 1.107.Remarque 1.113. Daprs les proprits de Cnonces dans le lemme prcdent (points (i) et (ii)),il faut noter que le projecteur Cest une fermeture (voir dnition 1.52).Proprits 1.114. Si C : A est une application rsiduable, alorsImC= ImC

.Dmonstration. Daprs (1.7), C

= (C

C) C

, alors ImC

ImC

C. Mais, ImC

C ImC

,par consquent ImC

C = ImC

.1.13.2 Projection dans limage dune applicationProposition 1.115 (Projection dans limage dune application). Soient B: | Aune applicationrsiduableetunlment x A. Leplusgrandlment x

ImBpluspetitquexestdonnparB B

(x). En dautres termes, B = B B

est un projecteur dans limage de B.Dmonstration. Le lecteur trouvera une dmonstration de ce rsultat dans [Cohen et al., 1996].Proprits 1.116. Si B : | Aest une application rsiduable, alorsImB= ImB.Dmonstration. Daprs (1.7), B = (BB

)B, alors ImB Im_B B

_. Mais, Im_B B

_ ImB,par consquent Im_B B

_= ImB.CHAPITRE1 Outils algbriques 311.13.3 Projecteurs dans limage dune application paralllement au noyau dune autreapplicationSoient B : | Aet C : A Adeux applications. Dans [Cohen et al., 1996, Cohen et al., 1997],les auteurs sintressent au problme suivant : pour tout x A, existe-t-il un y ImB[x]C, autrementdit, cela revient chercher un y A, tel queu | : C(y) = C(x),B(u) = y.Si llment y satisfaisant ces conditions existe, et si de plus il est unique, alors y correspond la projec-tion de x dans limage de B paralllement au noyau de C, et le projecteur correspondant est alors donnparCB= B (C B)

C. (1.30)Toujours dans [Cohen et al., 1996, Cohen et al., 1997], les auteurs sintressent au problme de lexis-tence dune telle projection, cest--dire est-ce que CB CB = CB ce qui revient dire que ImB [x]Cestnonvide.Demme,danslecasocetteprojectionexiste,lesauteurssintressentauproblmede lunicit, en dautres termes, ils cherchent savoir si ImB [x]Cest un singleton. Nous rappelonsci-dessous, ces conditions dexistence et dunicit.Lexistence du projecteur pour tout x est quivalente la condition C = C CB (cest--dire que= CB(x) est dans la mme classe dquivalence que x modker C), ou encore la conditionImB = Im(C B).Lunicit du projecteur est quivalente la conditionB=CB B(cest--dire que pour toutx ImB, celui-ci reste invariant par CB), ou encore que ker B = ker (C B).Dans le cas o les applications linaires B et C du projecteur 1.30 sont reprsentes par leur matrice,il est galement montr que si lexistence et lunicit de la projection sont garanties, alors lexpression(1.30) du projecteur devient :CB= (B/(CB)) C = B((CB)C) .Notons que dans le cas dapplications rsiduables, mme si lexistence et lunicit ne sont pas vri-es, il est possible de donner une interprtation au projecteur (1.30). En effet, ce projecteur se dcom-pose en deux applications. Tout dabord, llment z =C

C(x) est le plus grand lment dans [x]C.Ce qui entrane que=B B

(z) est le plus grand lment dansImB qui soit plus petit quez. Parconsquent, nous avons C() _ C(x) ; dans [Cohen et al., 1998b] le terme sous-quivalent est employpour qualier cet lment .1.13.4 quations implicites linaires dans les diodesDans cette partie on sintresse la rsolution dinquations implicites de la forme :x _ (x) b (1.31)x _ (x) b. (1.32)Thorme 1.117. Soient (T, , ) et : T T une application semi-continue infrieurement (cf.dnition 1.33). La plus petite solution de lquation (1.31) est x = (b), o0= IdD, n= . . . . .n foiset = nNn= IdD nNn+1.32 CHAPITRE1 Outils algbriquesDe plus, x = (b) ralise lgalit dans x _ (x) b.Dmonstration. On montre dabord que (b) est un minorant des solutions de (1.31). Par induction onax _ (x) b _ ((x) b) b _ . . . _ k(x) k1

t=0t(b) _ (b) k 0.Dautre part, puisque est semi-continue infrieurement et daprs la proprit de distributivit innie(cf. Dnition 1.85),((b)) b = b _

nNn(b)_= b

nNn+1(b) = (b)donc (b) est bien solution de lquation implicite x = (x) b.Corollaire 1.118. Soit T un diode complet ; si = La, T T, alors lquation implicitex = a x b (1.33)admet x = ab =

k0akb comme plus petite solution.Thorme 1.119. Soient T un diode complet et : T T une application semi-continue suprieure-ment. La plus grande solution de (1.32) est x = (b) avec=_nNn.Dmonstration. Comme est s.c.s., on a :((b)) b = _

nNn(b)_ b =

nN(n(b)) b =

n1n(b) Id(b) = (b),ce qui montre que (b) est solution de (1.32). De plus quelle que soit x solution de x = (x) b, on ax = (x)b = ((x) b)b = . . . = n(x)n1(b). . . (b)b _ n1(b). . . (b)b.On en dduit que toute solution de (1.32) est infrieure ou gale (b).Corollaire 1.120. Soit lapplication =L

a :x a x, T T dnie sur un diode complet. Alors,lquationx = a x badmet x = (b) = a b =_

nNan_ b comme plus grande solution.Les applications / et T(cf. notation 1.99) vrient les relations suivantes (voir [Gaubert, 1992] et[Cottenceau, 1999]).CHAPITRE1 Outils algbriques 33Thorme 1.121. Soit T un diode complet. a, b Ta+_ a(1.34)(a)= a(1.35)(a+)= a(1.36)a(ba)= (ab)a (1.37)(a b)= (ab)a = b(ab) = (a b)a = b(a b)(1.38)aa= a(1.39)(a)+= a(1.40)(a+)+= a+(1.41)(ab)+= a(a b)(1.42)(ab)= e a(a b)(1.43)En outre, lorsque T est commutatif(a b) = ab. (1.44)Dmonstration.(1.34) par dnition a = e a+a _ e et a _ a+.(1.35) par dnition de ltoile de Kleene, (a) = k0

l0_ak_l= k0

l0ak+l=

j=k+l0aj= a.(1.36) par dnition de T, a _a+a_(a+), (isotonie de /). Daprs (1.34), a+_a(a+) _ (a) = a (par (1.35)). On en dduit que a _ (a+) _ (a) = a do lgalit.(1.37) (ab)a = (e ab abab . . .)a = (aabaababa. . .) = a(e bababa. . .) = a(ba).(1.38) daprs le corollaire 1.118, sont quivalents :x = (a b)x = (a b)x e = ax bx ex = abx ax = (ab)a = (ab)aa = (a b)a.De mme pour lautre galit, x = (ab) = axbxe = baxb = b(ab) = bb(ab) =b(a b).(1.39) daprs (1.38) et en raison de lidempotence de , a = (aa) = (aa)a = (a+)a = aa(par (1.36)).(1.40) par dnition de T, a+= aa, donc (a)+= a(a) = aa = a (par (1.35) et (1.39)).(1.41) par dnition, a+= aa, alors (a+)+= a+(a+) = a+a = aaa = aa = a+(par (1.39)).(1.42) (ab)+= ab(ab) = a (b(ab)) = a(a b) (par (1.38)).(1.43) (ab) = e (ab)+= e a(a b) (par 1.42).(1.44) Si T est commutatif on a pour k 1, (ab)k= (a)kbk=abk(par (1.40)). Do (a b) =(ab)a = (e k1abk)a = a k1abk= a(e k1bk) = ab.34 CHAPITRE1 Outils algbriquesLes rsultats noncs par le thorme 1.121 sont vris pour tout diode complet, y compris ma-triciel. Dans le cas matriciel, on a en particulier le rsultat suivant permettant de calculer ltoile dunematrice dcompose en 4 blocs.Thorme 1.122. Soit A Tnnpartitionne en quatre blocsA =_a11a12a21a22_La matrice A scrit alors_a11a11a12(a21a11a12a22)a21a11a11a12(a21a11a12a22)(a21a11a12a22)a21a11(a21a11a12a22)_.Dmonstration. on renvoie le lecteur [Cohen et al., 1989] ou [Baccelli et al., 1992] pour ce rsultat.1.13.5 Rsiduation matricielleLemme 1.123 ([Baccelli et al., 1992]). Si A = (Aij) Tmno T est un diode dans lequel existe,et y Tm, alors(A y)i=m_j=1(Aji yj).Quand T = Zmax, alors on obtient(Ay)i=m_j=1(Ajiyj) = minj=1,...,m(Aji +yj).Thorme 1.124. Soient A, D Tmn, B Tmpet C Tnp, alors daprs le lemme prcdenton obtient pour C = A B et D = B /C :Cij =m_k=1(Aki Bkj) , Dij =p_k=1(Bik /Cjk) . (1.45)La remarque suivante est due [Cohen, 1998a].Remarque 1.125. Il est important de noter que certaines expressions impliquant la rsiduation peuventtre ambigus. ConsidronsA Tmn, B Tmpetx Tp, il faut tre prudent quand on utilisedes expressions comme A Bx. En effet, dun ct, remarquons que A (Bx) peut tre interprte commeL

A LB(x). Cette application L

A LB nest en gnral pas un morphisme de TpTn, mais parisotonie elle vrieL

A LB(x y) _ L

A LB(x) L

A LB(y).Mais, dun autre ct, x (A B)x peut tre interprte comme un oprateur linaire de Tp Tn,car en fait cet oprateur correspond la multiplication gauche par C = A B (voir (1.45)).Par contre, daprs (f.8), on a toujours L

A LB _ A B car A (Bx) _ (A B)x.Thorme 1.126 ([Cohen et al., 1991]). Soient T un diode complet et A Tpnune matrice. AlorsA A est une matrice dans TnnvriantA A = (A A). (1.46)CHAPITRE1 Outils algbriques 35Dmonstration. Daprs (f.2), AA _E, o E est la matrice identit de Tnn. Dautre part, daprs(f.3), A = A(AA) donc AA = A(A(AA)). Or daprs (f.8), A(A(AA)) _ AAAA. On peutdonc tablir lencadrement suivantE _ (AA)2_ AA,de mme pour tout n 1, E _ (AA)n_AA. Par sommation on obtient donc (AA)=AA. Enposant AA =B avec B Tnnune matrice, une autre faon dinterprter ce rsultat est de dire quelapplication x Bx est une fermeture.1.14 ConclusionCe chapitre introductif a permis de dresser la liste des outils mathmatiques qui seront utiliss par lasuite. Il sagit dun pralable la commande des GET prsente dans les chapitres suivants. Nous avonsnotamment trac un panorama gnral sur la rsiduation et ses applications aux diodes. Nous avonsgalement pu constater que certaines applications non rsiduables a priori, pouvaient ltre malgr tout,en considrant des restrictions sur leur domaine de dnition. Une classe importante dapplications nonrsiduables est galement tudie : les fermetures. Sur les fermetures, le principal rsultat est quil estpossible de munir leur image dune structure de treillis et quil est alors possible de considrer des res-trictions rsiduables pour certaines fermetures.Le chapitre suivant est tout dabord consacr la modlisation de systmes vnements discretspar des rseaux de Petri et plus particulirement par une sous-classe des rseaux de Petri : les graphesdvnements temporiss. Ensuite, diffrentes reprsentations pour les graphes dvnements temporissrencontres dans la littrature (reprsentation aux dateurs, aux compteurs, par des sries formelles) sonttudies.CHAPITRE 2Comportement linairedes GET dans les diodes2.1 IntroductionLtude des systmes vnements discrets (SED) constitue, depuis bientt 30 ans, un domaine derecherche trs actif (de par son intrt thorique et conomique) ayant donn lieu de nombreuses publi-cations. De cette littrature se dgagent de multiples classes de systmes mettant en jeu des phnomnesde natures diffrentes : paralllisme, saturation, synchronisation, exclusion mutuelle, choix, squence-ment . . ., et autant de modles mathmatiques.Dans ce mmoire nous considrons les systmes qui admettent un modle linaire dans les structuresalgbriques introduites dans le chapitre prcdent. Il sagit des systmes mettant en jeu des phnomnesde synchronisation et de retard que lon retrouve abondamment dans les systmes de transport (syn-chronisation de bus [Houssin, 2003]), les systmes informatiques [Le Boudec and Thiran, 2001] et lessystmes de production et plus particulirement dassemblage [Cohen et al., 1983, Cohen et al., 1985].La modlisation de ces systmes dans lalgbre des diodes et llaboration dune thorie des sys-tmes (max, +)-linaires analogue la thorie des systmes conventionnels a t loeuvre de lquipe(max, +) de lINRIA au cours des annes 80.Lobjectifdecechapitreestdeproposerunsurvoldecettethorieetnotammentderappelerlamodlisation des graphes dvnements temporiss dans les diodes de sries formelles. Ce chapitre estcompos comme suit.Tout dabordla modlisationde systmes vnements discrets par Rseauxde Petri (RdP)[David and Alla, 1989, Murata, 1989] est prsente. Ce survol est loccasion de rappeler la dnitiondune sous-classe des RdP, les Graphes dvnements Temporiss (GET).La suite est ddie la modlisation sous forme dtat de GET dans les diodes. Les rfrences quiont servi sa rdaction sont [Cohen et al., 1989, Baccelli et al., 1992].Puis la description entre-sortie des GET est aborde, il est notamment rappel que la trajectoire desortie dun systme (max, +)-linaire est le rsultat de la sup-convolution de la rponse impulsionnelledu systme et la trajectoire dentre.Ce chapitre se termine par lintroduction de transformes enetqui jouent un rle analogue la transforme enz des signaux discrets dans lalgbre conventionnelle. La transforme de la rponseimpulsionnelledunsystmelinaireconduittablirsamatricedetransfertdansundiodedes-riesformellesnot /axin[[, ]]. Lesouvragesderfrencepourcettepartiesont[Cohen et al., 1989,Cohen, 1998b].3738 CHAPITRE2 Comportement linaire des GET dans les diodes2.2 Modlisation de systmes vnements discrets par rseaux de Petri2.2.1 Les rseaux de PetriLes rseaux de Petri (RdP) ont t introduits par C.A. Petri en 1962 [Petri, 1962]. Ils constitu