# Notes de cours: Analyse, Simulation et Commande de systèmes (max,+)-linéaires.

Yannick Pencolé

► To cite this version:

Yannick Pencolé. Notes de cours: Analyse, Simulation et Commande de systèmes (max,+)-linéaires.. Master. Module Controle et Simulation (partie 1), Université Paul Sabatier, Toulouse, France. 2023, pp.58. hal-04775880

HAL Id: hal-04775880

https://laas.hal.science/hal-04775880v1

Submitted on 10 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Notes de cours: Analyse, Simulation et Commande de
systèmes (max, +)-linéaires
Module Contrôle et Simulation, partie 1
(8h cours-TD, 8h TP)

Yannick Pencolé

Novembre 2023
# Avertissement

Ce document sont des notes de cours largement inspirés de cours précédents qu'il me faut créditer par ordre de chronologie décroissant :

— Les notes de cours d'Euriell Le Corronc [Cor22]

— Les notes de cours de Laurent Houssin [Hou]

— Les notes de cours de Laurent Hardouin [Har08]

— Les notes de cours de Stéphane Gaubert [Gau99]

La référence essentielle à consulter si l'on veut aller plus loin dans la compréhension de l'algèbre (max, +) et son application aux systèmes à événements discrets est le livre intitulé Synchronization and linearity : an algebra for discrete event systems [BCOQ92]. La référence pour la théorie de la résiduation qui est abordée très brièvement dans ce cours est publié dans [BJ72].
# Chapitre 1

## Introduction

Considérons $x(t)$ un vecteur de $\mathbb{R}^n$ pour toute unité de temps $t \in \mathbb{N}$. L'évolution d'un système linéaire et autonome est régie par le système d'équations suivant :

$$x(t+1) = Ax(t), t \in \mathbb{N} \qquad (\text{théorie de la différence}) \qquad (1.1)$$

$$x(0) = x_0 \qquad (\text{condition initiale}) \qquad (1.2)$$

avec :

$$— x_0 \in \mathbb{R}^n,$$

$$— A = (a_{i,j}) \in \mathbf{Mat}_{n,n}(\mathbb{R}) \text{ autrement dit } a_{ij} \in \mathbb{R}, 1 \le i \le n, 1 \le j \le n$$

Si l'on décortique l'équation (1.1) pour obtenir la composante $x_i, i \in \{1, \dots, n\}$ de $x$, on a pour tout $t \in \mathbb{N}$ :

$$x_i(t+1) = \sum_{j=1}^{n} a_{ij} \times x_j(t), \qquad (1.3)$$

L'équation (1.3) s'appuie sur deux opérations :

— opération $\times$: propagation du temps $(a_{ij} \times x_j(t)$, il s'agit de l'apport de la composante $x_j(t)$ à la constitution de $x_i(t+1)$).

— opération $+$: aggrégation des composantes $(\Sigma)$

Dans les systèmes classiques, les opérations $+$ et $\times$ sont les opérations mathématiques usuelles dans $\mathbb{R}$. L'objectif de ce cours est d'étudier ce type d'équations mais en remplaçant les opérateurs usuels $+$ et $\times$ sur $\mathbb{R}$ par d'autres opérateurs $\oplus$ et $\otimes$ sur des espaces algébriques plus exotiques. Autrement dit, on va vouloir étudier des équations de la forme :

$$x_i(t+1) = \bigoplus_{j=1}^{n} a_{ij} \otimes x_j(t), \qquad (1.4)$$

où les éléments $x_i(t), i \in \{1, \dots, n\}, t \in \mathbb{N}$ sont des éléments d'un espace algébrique spécifique. Et bien entendu, on considérera la version de cette équation sous forme vectorielle :

$$x(t+1) = A \otimes x(t), \qquad (1.5)$$

où $A$ est une matrice carrée composée d'éléments appartenant à cet espace algébrique. Ce qui est important à comprendre ici est que l'équation (1.5) conserve par construction le caractère linéaire de l'évolution de $x(t)$ et les questions que l'on va traiter dans ce cours sont les suivantes :

1. existe-t-il d'autres espaces algébriques munis d'opérations $(\oplus, \otimes)$ qui puissent être exploités pour décrire l'évolution d'autres types de systèmes linéaires ?

2. si oui, en existe-il pour caractériser des systèmes à événements discrets ?
3. si oui, quel type d'espace algébrique ?

4. et quelle classe spécifique de systèmes à événements discrets ?

5. et enfin peut-on définir une théorie de la commande s'appuyant sur des représentations du type (1.1) pour commander un système à événement discret ?

Avant de rentrer dans les détails de ce cours, répondons brièvement à toutes ces questions :

1. Existe-t-il d'autres espaces algébriques munis d'opérations ($\oplus, \otimes$) qui puissent être exploités pour décrire l'évolution autres types de systèmes linéaires ?

Oui, la linéarité n'est pas intrinsèque aux opérations usuelles $+$ et $\times$ de $\mathbb{R}$. Il existe d'autres espaces munis d'autres opérateurs qui vont avoir cette propriété.

2. Si oui, en existe-il pour caractériser des systèmes à événements discrets ?

Oui, ils ont été découverts dans les années 80-90 et ils portent le nom populaire d'algèbre des sandwichs (article Pour la Science (2005)) mais dans la communauté scientifique, ces espaces algébriques sont regroupés sous le nom d'algèbre (max, +) (l'explication de ce nom sera donnée ultérieurement après avoir introduit les éléments pour le comprendre).

3. Si oui, quel type d'espace algébrique ?

Les algèbres (max, +) sont des espaces de type *dioïde*.

4. Et quelle classe spécifique de systèmes à événements discrets ?

Un dioïde peut notamment servir à caractériser les Graphes d'Événements Temporisés (forme de réseau de Petri temporisé).

5. Et enfin peut-on définir une théorie de la commande s'appuyant sur des représentations du type (1.1) pour commander un système à événement discret ?

Oui et on présentera l'une d'entre elle, la *commande en juste à temps*.
# Chapitre 2

## Algèbre (max, +)

Le premier objectif dans ce cours est de présenter les bases de l'algèbre (max, +), ce qui va consister dans un premier temps à donner une définition formelle d'un dioïde et de savoir manipuler ses opérations de compositions internes (les fameux opérateurs $\oplus$ et $\otimes$).

### 2.1 Dioïde

Un dioïde est une structure algébrique que l'on peut définir à l'aide de structures algébriques plus élémentaires, les monoïdes.

**Définition 1 (Monoïde).** Un monoïde $(E, *)$ est un magma unifère associatif, autrement dit :

1. un ensemble $E$ muni d'une loi de composition interne :

$$ \forall x, y \in E, x * y \in E \quad (\text{magma}) $$

2. il possède un élément neutre $e$ :

$$ \forall x \in E, e * x = x * e = x \quad (\text{unifère}) $$

3. la loi $*$ est associative

$$ \forall x, y, z \in E, x * (y * z) = (x * y) * z \quad (\text{associatif}) $$

La structure de monoïde est notamment la structure fondamentale permettant de définir la théorie des langages.

- Considérons un alphabet de symboles $(\{a, b, c, \dots\})$

- Soit $M$ l'ensemble des séquences finies de symboles sur cet alphabet :

$$ M = \{\varepsilon, a, b, c, a.a, a.b, a.c, \dots, a.a.a, a.a.b, \dots\} $$

- On définit l'opération de concaténation. qui, à un couple de séquences $(s_1, s_2)$, associe la séquence $s_1s_2$

- On définit $\lambda$ la séquence vide.

Alors la structure $(M, \cdot)$ avec $\lambda$ pour élément neutre constitue un monoïde, en effet :

1. la concaténation de deux séquences de $M$ forme une séquence de $M$ :

$$ \forall s_1, s_2 \in M, s_1 \cdot s_2 \in M $$

la concaténation est donc bien une loi de composition interne à $M$;

2. la séquence vide $\varepsilon$ est bien un élément neutre :

$$ \forall s \in M, \lambda \cdot s = s \cdot \lambda = s; $$
3. et la concaténation est associative :

$$
\forall s_1, s_2, s_3 \in M, (s_1.s_2).s_3 = s_1.(s_2.s_3).
$$

**Définition 2 (Monoïde commutatif).** *Un monoïde est $(E,*)$ est commutatif si sa loi interne $*$ est commutative :

$$
\forall x, y \in E, x * y = y * x
$$

Le monoïde de séquences (M, .) n'est pas commutatif : par exemple a.b ≠ b.a.

**Définition 3 (Semi-anneau).** *Un semi-anneau est une structure algébrique $(E, \oplus, \otimes)$ telle que :*

— $(E, \oplus)$ est un monoïde commutatif d'élément neutre $\varepsilon$ :

$$
\forall x \in E, x \oplus \varepsilon = \varepsilon \oplus x = x
$$

— $(E, \otimes)$ est un monoïde d'élément neutre $e$ :

$$
\forall x \in E, x \otimes e = e \otimes x = x
$$

— $\otimes$ est distributif par rapport à $\oplus$ :

$$
\forall x, y, z \in E,
$$

$$
x \otimes (y \oplus z) = (x \otimes y) \oplus (x \otimes z)
$$

$$
(x \oplus y) \otimes z = (x \otimes z) \oplus (y \otimes z)
$$

— L'élément neutre $\varepsilon$ de l'addition $\oplus$ est absorbant pour le produit $\otimes$ :

$$
\forall x \in E : x \otimes \varepsilon = \varepsilon \otimes x = \varepsilon.
$$

Afin d'illustrer la notion de semi-anneau, nous allons en construire un en partant du même
principe que pour le monoïde des séquences.

1. Soit $E$ l'ensemble des ensembles de séquences finies sur un alphabet fini $\{a, b, c, \dots\}$.
Autrement dit,

$$
E = \{\emptyset, \{\lambda\}, \{\lambda, a\}, \dots, \{abbaa, cbcc\}, \dots\}
$$

2. On définit $\otimes$ comme la concaténation d'ensembles de séquences, par exemple :

$$
\{ab, c\} \otimes \{d, ba\} = \{abd, abba, cd, cba\}
$$

3. On définit $\oplus = \cup$ comme l'union d'ensembles de séquences, par exemple :

$$
\{ab, c\} \cup \{d, ba\} = \{ab, c, d, ba\}
$$

4. L'élément neutre $\varepsilon$ de $\oplus$ est l'ensemble vide $\emptyset$ :

$$
\forall x \in E, x \cup \emptyset = \emptyset \cup x = x
$$

5. L'élément neutre $e$ de $\otimes$ est l'ensemble ne contenant que la séquence vide $\lambda$ autrement dit $e = \{\lambda\}$

$$
\{ab, c\} \otimes \{\lambda\} = \{ab, c\} = \{\lambda\} \otimes \{ab, c\}
$$

En s'appuyant sur les définitions précédentes, on remarque alors les propriétés suivantes :

— $(E, \oplus)$ d'élément neutre $\varepsilon = \emptyset$ est bien un monoïde commutatif ($\oplus = \cup$ or l'union d'ensembles est associative et commutative).

— $(E, \otimes)$ d'élément neutre $e = \{\lambda\}$ est bien un monoïde (le produit est associatif).
— $\otimes$ est distributif par rapport à $\oplus$ :

$$ \begin{aligned} \{ab\} \otimes (\{cb, ac\} \oplus \{d\}) &= \{ab\} \otimes \{cb, ac, d\} = \{abcb, abac, abd\} \\ (\{ab\} \otimes \{cb, ac\}) \oplus (\{ab\} \otimes \{d\}) &= \{abcb, abac\} \oplus \{abd\} = \{abcb, abac, abd\} \end{aligned} $$

— L'élément neutre de $\oplus$ (l'ensemble vide) est absorbant pour le produit $\otimes$, par exemple :

$$ \{ab, bc\} \otimes \emptyset = \emptyset. $$

L'ensemble $E$ muni des opérateurs et des éléments neutres précédemment définis forme ainsi un demi-anneau. Il est à remarquer qu'un élément $x$ de $E$ est un ensemble de séquences finies. Un tel élément $x$ est donc un langage régulier sur l'alphabet considéré et correspond donc un automate (automate qui reconnaît ce langage). Ainsi, un semi-anneau a l'expressivité nécessaire pour representer l'ensemble des automates, à la différence du monoïde $(M, \cdot)$ vu précédemment qui ne pouvait représenter que des séquences (un seul mot de langages).

Un dioïde est un semi-anneau particulier, il combine ainsi deux monoïdes (d'où le terme dioïde)

**Définition 4** (Dioïde). *Un dioïde* $(\mathcal{D}, \oplus, \otimes)$ *est un semi-anneau idempotent, autrement dit, c'est un semi-anneau tel que :*

$$ \forall x \in \mathcal{D}, x \oplus x = x. $$

Ce qui fait la particularité d'un dioïde par rapport à un semi-anneau classique est l'idempotence de l'addition qui est une des propriétés fondamentales des représentations type $(\max,+)$.
Comme nous le verrons plus tard, c'est cette propriété qui nous permettra de représenter une classe spécifique de systèmes à événements discrets. Le semi-anneau des automates que nous avons défini précédemment est un dioïde car l'union d'ensembles est idempotente, par exemple :

$$ \{ab, bc\} \cup \{ab, bc\} = \{ab, bc\} $$

**Définition 5** (Dioïde commutatif). *Un dioïde* $(\mathcal{D}, \oplus, \otimes)$ *est commutatif si le monoïde sous-jacent* $(\mathcal{D}, \otimes)$ *est commutatif :*

$$ \forall x, y \in \mathcal{D}, x \otimes y = y \otimes x $$

Remarquez que le dioïde étant un demi-anneau, son addition est commutative, ce qui signifie que dans un dioïde commutatif, les deux opérations sont commutatives. Notez également que le dioïde des automates n'est pas commutatif car l'opération de concaténation d'ensembles ne l'est pas :

$$ \{ab, bc\} \otimes \{c\} = \{abc, bcc\} \neq \{cab, cbc\} = \{c\} \otimes \{ab, bc\} $$

Dans la suite de ce cours, les dioïdes que nous considérerons seront toujours commutatifs.

**Pourquoi appelle-t-on ce type d'algèbre exotique ?** Un dioïde n'est qu'un semi-anneau idempotent. Ce n'est donc pas un anneau. Pour être un anneau, il faudrait que le monoïde $(\mathcal{D}, \oplus)$ soit en fait un groupe, autrement dit, chaque élément $x$ de $\mathcal{D}$ devrait pouvoir être associé à un inverse $x^{-1}$ tel que $x \oplus x^{-1} = e$. Dans les algèbres que nous manipulons dans ce cours, les notions d'inverse et d'inversibilité n'existent pas. On va devoir s'en passer ! Vous pouvez déjà imaginer les conséquences de l'absence de l'inversibilité.
## 2.2 Exemples de dioïdes

### 2.2.1 Dioïde $\mathbb{R}_{max}$

On considère l'ensemble des réels $\mathbb{R}$ augmenté du symbole $-\infty$ que l'on note $\bar{\mathbb{R}} = \mathbb{R} \cup \{-\infty\}$. Le dioïde $\mathbb{R}_{max}$ est défini comme suit :

$$ \mathbb{R}_{max} = (\bar{\mathbb{R}}, \oplus, \otimes). \qquad (2.1) $$

tel que :

$$ \text{— } \oplus = \max $$

$$ \text{— } \otimes = + $$

$$ \text{— } \varepsilon = -\infty $$

$$ \text{— } e = 0 $$

Démontrons que $\mathbb{R}_{max}$ est effectivement un dioïde.

1. Considérons $\bar{\mathbb{R}}$ muni de l'opération max. Pour tout $x, y \in \bar{\mathbb{R}}$, $\max(x, y)$ est soit $x$, soit $y$ donc $\max(x, y) \in \bar{\mathbb{R}}$. ($\bar{\mathbb{R}}, \max$) est donc un magma. On a posé pour élément neutre $\varepsilon = -\infty$ or $\forall x \in \bar{\mathbb{R}}, \max(-\infty, x) = \max(x, -\infty) = x$. ($\bar{\mathbb{R}}, \max$) est donc un magma unifère. De plus max est associative :

$$ \forall x, y, z \in \bar{\mathbb{R}}, \max(\max(x, y), z) = \max(x, \max(y, z)). $$

Par conséquent ($\bar{\mathbb{R}}, \max$) est un monoïde. De plus il est commutatif :

$$ \forall x, y \in \bar{\mathbb{R}}, \max(x, y) = \max(y, x). $$

2. Considérons maintenant $\bar{\mathbb{R}}$ muni de l'opération +. Pour tout $x, y \in \bar{\mathbb{R}}, x + y \in \bar{\mathbb{R}}$ (on pose que $-\infty + x = -\infty$). ($\bar{\mathbb{R}}, \max$) est donc un magma. On a posé pour élément neutre $e = 0$ or $\forall x \in \bar{\mathbb{R}}, x + 0 = 0 + x = x$. ($\bar{\mathbb{R}}, +$) est donc un magma unifère. De plus + est associative :

$$ \forall x, y, z \in \bar{\mathbb{R}}, (x + y) + z = x + (y + z). $$

Par conséquent ($\bar{\mathbb{R}}, +$) est un monoïde.

3. + est distributif par rapport à max. Pour s'en convaincre, il suffit de l'écrire :

$$ \forall x, y, z \in \bar{\mathbb{R}}, x + \max(y, z) = \max(x + y, x + z) $$

$$ \forall x, y, z \in \bar{\mathbb{R}}, \max(x, y) + z = \max(x + z, y + z) $$

4. On a posé explicitement que $-\infty + x = -\infty$ donc $-\infty$ est absorbant pour +.

5. Par définition max est idempotent :

$$ \forall x \in \bar{\mathbb{R}}, \max(x, x) = x $$

Les 5 conditions précédentes ainsi établies, $\mathbb{R}_{max}$ est un dioïde par définition. De plus on peut remarquer que $\mathbb{R}_{max}$ est commutatif : en effet l'addition est commutative dans $\bar{\mathbb{R}}$. Le dioïde $\mathbb{R}_{max}$ est à l'origine de l'expression *algèbre* ($\max, +$) mais l'expression *algèbre* ($\max, +$) est générique, elle regroupe tout type de dioïde et tout type de calculs sur ces dioïdes.
### 2.2.2 Dioïde $\mathbb{R}_{min}$

On peut également définir le dioïde $\mathbb{R}_{min} = (\mathbb{R}^{+\infty}, \min, +)$ où $\mathbb{R}^{+\infty} = \mathbb{R} \cup \{+\infty\}$ tel que :

$$- \varepsilon = +\infty$$

$$- e = 0.$$

De manière identique à la démonstration précédente, on peut démonter que $\mathbb{R}_{min}$ est un dioïde commutatif.

### 2.2.3 Dioïdes $\mathbb{Z}_{min}$ et $\mathbb{Z}_{max}$

On peut également définir des dioïdes sur les entiers relatifs $\mathbb{Z}$ munis des mêmes opérateurs que $\mathbb{R}_{min}$ et $\mathbb{R}_{max}$. Soit $\mathbb{Z}^{-\infty} = \mathbb{Z} \cup \{-\infty\}$ et $\mathbb{Z}^{+\infty} = \mathbb{Z} \cup \{+\infty\}$, on peut définir les deux dioïdes suivants :

$$- \text{le dioïde } \mathbb{Z}_{min} = (\mathbb{Z}^{+\infty}, \min, +) \text{ avec } e = 0 \text{ et } \varepsilon = +\infty;$$

$$- \text{le dioïde } \mathbb{Z}_{max} = (\mathbb{Z}^{-\infty}, \max, +) \text{ avec } e = 0 \text{ et } \varepsilon = -\infty.$$

### 2.2.4 Dioïde $\mathbb{B}$

Il existe également le dioïde des Booléens (ensemble $\{1,0\}$).

$$\mathbb{B} = (\{1,0\}, +, \cdot)$$

où

$$- \text{ l'opération } + \text{ est la disjonction (ou) : } 0 + 1 = 1, 1 + 1 = 1, 1 + 0 = 1, 0 + 0 = 0;$$

$$- \text{ l'opération } \cdot \text{ est la conjonction (et) : } 0 \cdot 1 = 0, 1 \cdot 1 = 1, 1 \cdot 0 = 0, 0 \cdot 0 = 0.$$

$$- \text{ l'élément neutre pour } + \text{ est } \varepsilon = 0;$$

$$- \text{ l'élément neutre pour } \cdot \text{ est } e = 1.$$

Démontrons que $\mathbb{B}$ est effectivement un dioïde de la même façon que nous l'avons fait pour $\mathbb{R}_{max}$.

1. Considérons l'ensemble des Booléens $\{1,0\}$ munis de l'opération (+). Pour tout $x, y \in \{1,0\}$, $x + y \in \{1,0\}$ par définition. Donc $\{1,0\}, +$ est un magma. On a posé pour élément neutre $\varepsilon = 0$ or $\forall x \in \{1,0\}, 0 + x = x + 0 = x$. $\{1,0\}, +$ est donc un magma unifère. De plus + est associative :

$$\forall x, y, z \in \{1,0\}, x + (y + z) = (x + y) + z.$$

Par conséquent $(\{1,0\}, +)$ est un monoïde. De plus il est commutatif :

$$\forall x, y \in \{1,0\}, x + y = y + x.$$

2. Considérons maintenant les Booléens munis de l'opération ($\cdot$). Pour tout $x, y \in \{1,0\}$, $x \cdot y \in \{1,0\}$ par définition. $(\{1,0\}, \cdot)$ est donc un magma. On a posé pour élément neutre $e = 1$ or $\forall x \in \{1,0\}, x \cdot 1 = 1 \cdot x = x$. Par conséquent, $(\{1,0\}, \cdot)$ est un magma unifère. De plus l'opération ($\cdot$) est associative :

$$\forall x, y, z \in \{1,0\}, (x \cdot y) \cdot z = x \cdot (y \cdot z).$$

Par conséquent $(\{1,0\}, \cdot)$ est un monoïde.

3. L'opération ($\cdot$) est distributive par rapport à +. Pour s'en convaincre, il suffit de l'écrire :

$$\forall x, y, z \in \{1,0\}, x \cdot (y + z) = (x \cdot y) + (x \cdot z)$$

$$\forall x, y, z \in \{1,0\}, (x + y) \cdot z = (x + z) \cdot (y + z)$$
4. L'élément neutre $\varepsilon = 0$ est absorbant pour le produit $\cdot$

$$ \varepsilon \cdot 1 = 0, \varepsilon \cdot 0 = 0. $$

5. Par définition le produit $\cdot$ est idempotent :

$$ 0 \cdot 0 = 0, 1 \cdot 1 = 1. $$

On remarque enfin que $\mathbb{B}$ est commutatif car le produit $\cdot$ est également commutatif. Le dioïde $\mathbb{B}$ est élémentaire mais il est fondamental pour la construction de dioïdes plus complexes de séries formelles (hors-programme : $\mathbb{B}[[x_1, \dots, x_n]]$).

### 2.2.5 Dioïdes complets

Dans notre recherche d'un espace algébrique pouvant être exploité pour analyser des systèmes (max, +)-linéaires, nous devons être en mesure d'utiliser non seulement des expressions de taille finie mais également de taille infinie (pour l'analyse de comportements asymptotiques par exemple). Par exemple, dans un dioïde $\mathcal{D}$, on doit garantir que des expressions du style

$$ \bigoplus_{x \in A \subseteq \mathcal{D}} x $$

soient définies dans $\mathcal{D}$ sachant que $A$ peut être un sous-ensemble infini de $\mathcal{D}$ (la somme en question est donc une somme infinie). Il nous faut donc garantir que de telles expressions sont parfaitement définies dans ces espaces. C'est dans le cadre des dioïdes complets que nous garantissons l'existence de telles expressions.

**Définition 6 (Dioïde complet).** *Un dioïde $(\mathcal{D}, \oplus, \otimes)$ est complet si*

— il est fermé pour les sommes infinies :

$$ \forall A \subseteq \mathcal{D}, \bigoplus_{j=1, x_{ij} \in A}^{+\infty} x_{ij} \in \mathcal{D} $$

— et si la loi $\otimes$ distribue sur les sommes infinies, c'est-à-dire si pour tout $c \in \mathcal{D}$, on a :

$$ \forall A \subseteq \mathcal{D}, c \otimes \left( \bigoplus_{j=1, x_{ij} \in A}^{+\infty} x_{ij} \right) = \bigoplus_{j=1, x_{ij} \in A}^{+\infty} (c \otimes x_{ij}). $$

Parmi les éléments d'un dioïde complet, un élément se distingue, c'est la somme de tous les éléments de $\mathcal{D}$. Cet élément existe nécessairement dans $\mathcal{D}$ même si la cardinalité de $\mathcal{D}$ est infinie car $\mathcal{D}$ est complet :

$$ \tau = \bigoplus_{x \in \mathcal{D}} x \qquad (2.2) $$

De cette définition de $\tau$, on a immédiatement le résultat suivant, à savoir que $\tau$ est absorbant pour l'addition $\oplus$ :

$$ \forall x \in \mathcal{D}, \tau \oplus x = \tau. \qquad (2.3) $$

En effet,
$$ \tau \oplus x = \left( \bigoplus_{y \in \mathcal{D}} y \right) \oplus x \qquad (2.4) $$

$$ = \left( \left( \bigoplus_{y \in \mathcal{D} \setminus \{x\}} y \right) \oplus x \right) \oplus x \qquad (2.5) $$

$$ = \left( \bigoplus_{y \in \mathcal{D} \setminus \{x\}} y \right) \oplus x \qquad (2.6) $$

$$ = \left( \bigoplus_{y \in \mathcal{D}} y \right) = \tau \qquad (2.7) $$

### 2.2.6 Exemples de dioïdes complets

Nous présentons ici quelques exemples de dioïdes complets.

**Dioïde $\mathbb{B}$:** Le dioïde $\mathbb{B}$ est complet en effet : $\bigoplus_{j=1}^{+\infty} x_j = 0$ si tous les $x_j$ sont égaux à 0, sinon cela vaut 1. La première condition est ainsi vérifiée. Regardons maintenant la deuxième condition. Supposons que $c = 0$,

$$ 0 \cdot \left( \bigoplus_{j=1, x_{ij} \in A}^{+\infty} x_{ij} \right) = 0 $$

et

$$ \bigoplus_{j=1, x_{ij} \in A}^{+\infty} (0 \otimes x_{ij}) = \bigoplus_{j=1, x_{ij} \in A}^{+\infty} 0 = 0. $$

Le deuxième cas est $c = 1$, on a :

$$ 1 \cdot \left( \bigoplus_{j=1, x_{ij} \in A}^{+\infty} x_{ij} \right) = \bigoplus_{j=1, x_{ij} \in A}^{+\infty} x_{ij} $$

et

$$ \bigoplus_{j=1, x_{ij} \in A}^{+\infty} (1 \otimes x_{ij}) = \bigoplus_{j=1, x_{ij} \in A}^{+\infty} x_{ij}. $$

La deuxième condition de la complétude de $\mathbb{B}$ est donc vérifiée. On peut enfin remarquer que sur le dioïde $\mathbb{B}$ on a :

$$ \tau = \bigoplus_{x \in \mathbb{B}} x = 1 \oplus 0 = 1 $$

**Extension du dioïde $\mathbb{R}_{max}$:** Le dioïde $\mathbb{R}_{max}$ n'est pas complet. Une façon de s'en convaincre est de calculer $\tau$. Sur $\mathbb{R}_{max}$, $\tau$ est défini par :

$$ \tau = \max_{x \in \mathbb{R}_{max}} (x) = \max_{x \in \mathbb{R}} (x) = +\infty $$
or $+\infty$ n'est pas un élément de $\overline{\mathbb{R}}^\infty$ par définition. Pour avoir un dioïde $\mathbb{R}_{max}$ complet, il faut modifier sa définition initiale pour inclure $+\infty$. Dans la suite de document, $\mathbb{R}_{max}$ désignera la version complète du dioïde ainsi (nouvellement) défini.

$$ \text{Soit } \overline{\mathbb{R}} = \mathbb{R} \cup \{-\infty\} \cup \{+\infty\}, $$

$$ \mathbb{R}_{max} = (\overline{\mathbb{R}}, \max, +) $$

avec $\varepsilon = -\infty, \varepsilon = 0$ puis les conventions suivantes :

$$ \text{— } \max(+\infty, +\infty) = +\infty \text{ (idempotence de } \oplus\text{)} $$

$$ \text{— } (-\infty) + (+\infty) = (+\infty) + (-\infty) = -\infty \text{ ($\varepsilon$ est absorbant pour } \otimes\text{)} $$

**Extensions du dioïde $\mathbb{R}_{min}$ :** Pour les mêmes raisons que ci-dessus, il faut étendre la définition de $\mathbb{R}_{min}$ pour le rendre complet.

$$ \mathbb{R}_{min} = (\overline{\mathbb{R}}, \min, +) $$

avec $\varepsilon = +\infty, \varepsilon = 0$ puis les conventions suivantes :

$$ \text{— } \min(-\infty, -\infty) = -\infty \text{ (idempotence de } \oplus\text{)} $$

$$ \text{— } (-\infty) + (+\infty) = (+\infty) + (-\infty) = +\infty \text{ ($\varepsilon$ est absorbant pour } \otimes\text{)} $$

Dans $\mathbb{R}_{min}$ complet, on a alors :

$$ \tau = \min_{x \in \mathbb{R}_{min}} (x) = -\infty. $$

**Extensions des dioïdes $\mathbb{Z}_{min}$ et $\mathbb{Z}_{max}$** Il faut également compléter $\mathbb{Z}_{min}$ et $\mathbb{Z}_{max}$ sur $\overline{\mathbb{Z}}$ pour avoir la complûtude de ces dioïdes en procédant comme pour $\mathbb{R}_{min}$ et $\mathbb{R}_{max}$.

## 2.3 Relation d'ordre dans un dioïde

### 2.3.1 Petits rappels sur les ensembles ordonnés

**Définition 7 (Relation d'ordre).** *Soit E un ensemble quelconque, une relation d'ordre R est une relation binaire sur E telle que :*

1. R est réflexive : $\forall x \in E, xRx$;

2. R est antisymétrique : $\forall x, y \in E, \text{ si } xRy \text{ et } yRx \text{ alors } x = y$;

3. R est transitive : $\forall x, y, z \in E, \text{ si } xRy \text{ et } yRz \text{ alors } xRz$.

En général une relation d'ordre est notée $\leq$ ou encore $\leq$. La relation d'ordre dont on parle ici n'est pas stricte. Une relation d'ordre stricte n'est qu'antisymétrique et transitive (pas réflexive). Une relation d'ordre peut être totale ($\forall x, y \in E, x \leq y$ ou $y \leq x$) autrement dit, elle impose un ordre à tous les couples d'éléments de E. Si une relation d'ordre n'est pas totale, on dit que la relation d'ordre est partielle : il existe alors des éléments x et y de E tels que :

$$ x \not\leq y \text{ et } y \not\leq x, $$

ces éléments x et y sont dits *incomparables*.

**Définition 8 (Ensemble ordonné).** *Un ensemble ordonné est un ensemble E muni d'une relation d'ordre $\leq$, on le note $(E, \leq)$.*

On dit que $(E, \leq)$ est totalement ordonné si la relation $\leq$ est totale. On dit également que $(E, \leq)$ est partiellement ordonné si la relation d'ordre $\leq$ est partielle.
### 2.3.2 Ordre induit par un dioïde

On considère ici un dioïde $(\mathcal{D}, \oplus, \otimes)$.

**Définition 9 (Relation $\leq$).** La relation $\leq$ sur le dioïde $\mathcal{D}$ est définie par :

$$ \forall x, y \in \mathcal{D}, x \leq y \Leftrightarrow x \oplus y = y. \qquad (2.8) $$

Nous allons montrer que cette relation est nécessairement une relation d'ordre sur $\mathcal{D}$.

**Théorème 1 (Relation d'ordre $\leq$).** Le dioïde $\mathcal{D}$ muni de la relation $\leq$ est un ensemble ordonné.

*Démonstration.* Nous devons démontrer que la relation $\leq$ remplit les trois conditions d'une relation d'ordre.

1. (Réflexivité). Pour tout $x$ de $\mathcal{D}$, on remarque que $x \oplus x = x$ car $\oplus$ est idempotente dans $\mathcal{D}$. Ainsi, par définition on a $x \leq x$.

2. (Antisymétrie). Pour tout $x, y$ de $\mathcal{D}$, supposons que $x \leq y$, cela implique que $x \oplus y = y$. Maintenant si on a en plus $y \leq x$, on a également l'égalité suivante $y \oplus x = x$ et donc $x = x \oplus y = y \oplus x = y$ (commutativité de $\oplus$).

3. (Transitivité). Pour tout $x, y, z$ de $\mathcal{D}$, supposons que $x \leq y$ et $y \leq z$. Comme $y \leq z$, on a $y \oplus z = z$. Ainsi $x \oplus z = x \oplus y \oplus z$. Sachant que $x \leq y$, on également que $x \oplus y = y$ ainsi $x \oplus z = y \oplus z$. Finalement on obtient $x \oplus z = z$, ainsi $x \leq z$.

□

Issu de cette preuve, on remarque que l'ordre $\leq$ existe sur le dioïde $\mathcal{D}$ grâce aux propriétés de commutativité et d'idempotence de $\oplus$. Sans la propriété d'idempotence, la réflexivité de $\leq$ disparaît et sans la commutativité on perd l'antisymétrie. Ainsi $\mathcal{D}$ ne pourrait pas être ordonné.<fnref n="1" /> Enfin, on peut remarquer que l'ordre $\leq$ n'est pas forcément total et peut n'être que partiel, en effet cela va dépendre de la loi $\oplus$. En général on a $z = x \oplus y$ et donc si $z \neq x$ et $z \neq y$ alors il n'y aucun ordre établi entre $x$ et $y$, ils sont incomparables dans ce cas.

Par la suite, nous aurons également l'occasion d'utiliser la notion $\geq$ :

$$ \forall x, y \in \mathcal{D}, x \geq y \Leftrightarrow y \leq x \qquad (2.9) $$

Une autre particularité de cette relation d'ordre est qu'elle induit l'isotonie des lois $\oplus$ et $\otimes$, autrement dit les lois $\oplus$ et $\otimes$ préservent l'ordre, elles sont isotones.

**Théorème 2 (Isotonie de $\oplus, \otimes$).** Soit $(\mathcal{D}, \oplus, \otimes)$ un dioïde quelconque, les lois $\oplus$ et $\otimes$ sont isotones par rapport à la relation d'ordre $\leq$, autrement dit, $\forall x, y, z \in \mathcal{D}$, si $x \leq y$ alors :

1. $x \oplus z \leq y \oplus z$

2. $x \otimes z \leq y \otimes z$

3. $z \otimes x \leq z \otimes y$

*Démonstration.*

1. Sachant que $x \leq y$, on a $x \oplus y = y$ et donc $x \oplus y \oplus z = y \oplus z$. On remarque que $x \oplus y \oplus z$ peut se réécrire $x \oplus z \oplus y \oplus z$, ainsi $x \oplus z \oplus y \oplus z = y \oplus z$ ce qui par définition nous donne $x \oplus z \leq y \oplus z$.

2. Puisque l'on a $x \oplus y = y$, on obtient $(x \oplus y) \otimes z = y \otimes z$. En distribuant, on obtient $(x \otimes z) \oplus (y \otimes z) = y \otimes z$ et donc par définition $x \otimes z \leq y \otimes z$.

3. Puisque l'on a $x \oplus y = y$, on obtient $z \otimes (x \oplus y) = z \otimes y$. En distribuant, on obtient $(z \otimes x) \oplus (z \otimes y) = z \otimes y$ et donc par définition $z \otimes x \leq z \otimes y$.

□

<footnote n="1">1. De cette manière du moins.</footnote>
### 2.3.3 Exemples

Revenons dans un premier temps sur le dioïde complet $\mathbb{R}_{max}$. Son ordre $\leq$ est donc défini ainsi :

$$ \forall x, y \in \mathbb{R}_{max}, x \leq y \Leftrightarrow \max(x, y) = y $$

On constate deux choses :

1. l'ordre de $\mathbb{R}_{max}$ suit l'ordre naturel sur les réels $\mathbb{R}$ : $x$ est plus petit que $y$ si le maximum des deux est $y$.

2. cet ordre est total : peu importe $x$ ou $y$, $\max(x, y)$ est soit $x$, soit $y$ ainsi on peut toujours décider entre $x \leq y$ et $y \leq x$.

L'ordre sur le dioïde complet $\mathbb{R}_{min}$ est défini comme suit :

$$ \forall x, y \in \mathbb{R}_{min}, x \leq y \Leftrightarrow \min(x, y) = y $$

Pour les mêmes raisons que pour l'ordre sur $\mathbb{R}_{max}$, l'ordre sur $\mathbb{R}_{min}$ est total, par contre il suit l'ordre inverse de celui des réels.

L'ordre de $\mathbb{B}$ est :

$$ \forall x, y \in \mathbb{B}, x \leq y \Leftrightarrow x + y = y. $$

On en déduit que $0 \leq 0$, $0 \leq 1$, $1 \leq 1$. L'ordre est donc également total.

### 2.3.4 Treillis d'un dioïde complet

Considérons tout d'abord un dioïde quelconque $(\mathcal{D}, \oplus, \otimes)$ et sa relation d'ordre induite $\leq$.

**Proposition 1** (Existence d'un plus petit majorant). *Soit $a, b \in \mathcal{D}$ alors $a \oplus b$ est le plus petit majorant de $a$ et de $b$ dans $\mathcal{D}$, autrement dit :*

1. $a \leq a \oplus b$;

2. $b \leq a \oplus b$;

3. *il n'existe pas de $c \in \mathcal{D}$ différent de $a \oplus b$ tel que $b \leq c$, $a \leq c$ et $c \leq a \oplus b$.*

*Démonstration.*

1. On rappelle que $c \leq d$ si et seulement si $c \oplus d = d$. On remarque que $a \oplus a \oplus b = a \oplus b$ (car $a \oplus a = a$). Donc $a \leq a \oplus b$.

2. De même $b \oplus a \oplus b = a \oplus b$. Donc $b \leq a \oplus b$.

3. Supposons qu'un tel $c$ existe. Comme $c \leq a \oplus b$, on a $c \oplus a \oplus b = a \oplus b$. Nous avons également que $a \leq c$ ce qui donne $a \oplus c = c$. Donc $c \oplus a \oplus b = c \oplus b = a \oplus b$. De même $b \leq c$ d'où $b \oplus c = c$. On obtient alors $c = a \oplus b$, d'où la contradiction.

$\square$

La présence d'un plus petit majorant nous permet d'affirmer qu'un dioïde quelconque $a$ également une structure de demi-treillis supérieur.

**Corollaire 1** (Demi-treillis supérieur). *L'ensemble ordonné $(\mathcal{D}, \leq)$ forme un demi-treillis supérieur, c'est-à-dire que tout couple $(a, b)$ d'éléments de $(\mathcal{D}, \leq)$ admet un plus petit majorant noté $a \lor b$ :*

$$ a \lor b = a \oplus b. $$
La question que l'on peut également se poser porte sur l'existence d'un plus grand minorant pour tout couple (a, b) de (D, ≤). Intuitivement, il faudrait considérer tous les éléments de D inférieurs à a et à b à la fois et prendre le plus grand d'entre eux. Le plus grand élément d'un ensemble s'obtient en additionant tous les éléments de l'ensemble, encore faut-il que cela soit possible. Le dioïde considéré étant quelconque, ce nombre d'éléments peut être infini et donc la somme de ces éléments peut être infinie. Cette contrainte impose donc qu'un tel plus grand minorant ne peut être défini que sur un dioïde complet.

**Proposition 2** (Existence d'un plus grand minorant dans un dioïde complet). *Soit $(\mathcal{D}, \oplus, \otimes)$ un dioïde complet, soit $a, b \in \mathcal{D}$ alors $a \wedge b = \bigoplus_{x|x \le a, x \le b} x$ est le plus grand minorant de $a$ et de $b$ dans $\mathcal{D}$, autrement dit :*

1. $a \wedge b \le a$;

2. $a \wedge b \le b$;

3. *il n'existe pas de $c \in \mathcal{D}$ différent de $a \wedge b$ tel que $c \le b, c \le a$ et $a \wedge b \le c$.*

*Démonstration.*

1. Considérons un élément $x$ de la somme $a \wedge b = \bigoplus_{x|x \le a, x \le b} x$. $x \le a$ si et seulement si $x \oplus a = a$. Donc

$$ (a \wedge b) \oplus a = \left( \bigoplus_{x|x \le a, x \le b} x \right) \oplus a \quad (2.10) $$

$$ = \bigoplus_{x|x \le a, x \le b} (x \oplus a) \quad (2.11) $$

$$ = \bigoplus_{x|x \le a, x \le b} a \quad (2.12) $$

$$ = a \quad (2.13) $$

Ainsi $a \wedge b \le a$.

2. Raisonnement similaire à celui ci-dessus en considérant $x \le b$.

3. Supposons qu'il existe un tel $c$. On a donc $c \le a$ et $c \le b$. Par définition $a \wedge b = (\bigoplus_{x|x \le a, x \le b} x)$ et donc $a \wedge b = (\bigoplus_{x|x \le a, x \le b, x \ne c} x) \oplus c$. Comme $a \wedge b \le c$, $(\bigoplus_{x|x \le a, x \le b, x \ne c} x) \oplus c \oplus c = c$ et par idempotence $(\bigoplus_{x|x \le a, x \le b, x \ne c} x) \oplus c = c$. Finalement $a \wedge b = c$, d'où la contradiction. $\square$

La présence d'un plus grand minorant nous permet d'affirmer qu'un dioïde complet a également une structure de treillis.

**Corollaire 2** (Treillis). *L'ensemble ordonné $(\mathcal{D}, \le)$ où $\mathcal{D}$ est complet forme un treillis, c'est-à-dire que tout couple $(a, b)$ d'éléments de $(\mathcal{D}, \le)$ admet :*

— un plus petit majorant noté

$$ a \vee b = a \oplus b \quad (2.14) $$

— un plus grand minorant noté

$$ a \wedge b = \bigoplus_{x \le a, x \le b} x. \quad (2.15) $$

*Démonstration.* Le corollaire 1 nous informe que $(\mathcal{D}, \le)$ est un semi-treillis supérieur. À cela, la proposition 2 montre également l'existence d'un plus grand minorant. D'où le résultat. $\square$
**Corollaire 3** (Borne supérieure du treillis). Soit $\mathcal{D}$ un dioïde complet, l'élément $\top$ est la borne supérieure du treillis :

$$ \forall x \in \mathcal{D}, x \leq \top \qquad (2.16) $$

*Démonstration.* Par définition, $\top = \bigoplus_{y \in \mathcal{D}} y = \bigoplus_{y \in \mathcal{D}, y \neq x} y \oplus x$ (équation (2.2)). Ainsi $x \oplus \top = x \oplus \bigoplus_{y \in \mathcal{D}, y \neq x} y \oplus x = \bigoplus_{y \in \mathcal{D}, y \neq x} y \oplus x = \top$. D'où le résultat. $\square$

Il est également à noter que le treillis a également une borne inférieure $\bot$ qui est $\bot = \varepsilon$ :

$$ \forall x \in \mathcal{D}, \bot = \varepsilon \leq x \leq \top = \bigoplus_{y \in \mathcal{D}} y $$

**Proposition 3.** On a l'équivalence suivante :

$$ a = a \wedge b \Leftrightarrow a \leq b \qquad (2.17) $$

*Démonstration.*

— (⇒) Si $a = a \wedge b$ alors $a = \bigoplus_{x \leq a, x \leq b} x$. Ainsi, $a \oplus b = \bigoplus_{x \leq a, x \leq b} x \oplus b = b$ car $(a \wedge b) \oplus b = b$. Donc $a \leq b$.

— (aby) Par définition, on a $a \wedge b = \bigoplus_{x \leq a, x \leq b} x$ Or $a \leq b$ et donc, $\{x \in \mathcal{D}, x \leq a \text{ et } x \leq b\} = \{x \in \mathcal{D}, x \leq a\}$. Par conséquent $a \wedge b = \bigoplus_{x \leq a} x = a$. $\square$

## 2.4 Résolution de $x = ax \oplus b$ dans les dioïdes complets

Comme nous l'avons vu en introduction, l'objectif est de pouvoir représenter et d'analyser des systèmes sous la forme d'une représentation d'états dans un espace algébrique de type dioïde. Il nous faut donc être capable d'étudier et de résoudre des équations linéaires (en $x$) du type

$$ x = ax \oplus b $$

dans un dioïde $\mathcal{D}$ ($x, a, b \in \mathcal{D}$). Cette étude sera menée sur des dioïdes complets. La première question à se poser est donc :

*existe-t-il une solution à cette équation ?*

La réponse est oui et en général il en existe plusieurs comme nous allons le montrer dans la sous-section suivante.

### 2.4.1 Existence d'une solution

Pour nous convaincre de l'existence d'une solution, on va tout d'abord introduire la fonction :

$$ f: \begin{array}{c} \mathcal{D} \\ x \end{array} \longrightarrow \begin{array}{c} \mathcal{D} \\ ax \oplus b \end{array} \qquad (2.18) $$

Montrer l'existence d'une solution à l'équation $x = ax \oplus b$ revient donc à montrer l'existence d'un *point fixe* pour la fonction $f$, on cherche $x$ tel que $f(x) = x$. L'existence d'un tel point fixe repose sur un théorème de point fixe dû à Alfred Tarski [Tar55] (voir également le détail dans l'annexe B pour les curieux).

**Théorème 3** (Théorème du point fixe dans un treillis). Soit $(E, \leq)$ un treillis complet, soit $f$ une fonction croissante de $E$ sur $E$, soit $P$ l'ensemble des points fixes de $f$ ($P = \{x | f(x) = x\}$), alors :
1. P n'est pas vide;

2. ($P, \leq$) forme un treillis complet;

3. le plus petit majorant de P est le plus petit majorant de $\{x|x \leq f(x)\}$

4. le plus grand minorant de P est le plus grand minorant de $\{x|f(x) \leq x\}$

Pour pouvoir exploiter ce théorème, nous devons d'abord nous assurer que nous disposons de tous les ingrédients nécessaires. Il nous faut d'abord un treillis complet : il nous est donné par le dioïde complet ($\mathcal{D}, \leq$). Il nous faut une fonction $f$ croissante de $\mathcal{D} \to \mathcal{D}$. La fonction que l'on souhaite étudier est $f(x) = ax \oplus b$. Or le théorème 2 affirme que le produit et l'addition sont isotones donc $f$ est bien croissante ($\forall x, x' \in \mathcal{D}, x \leq x' \Rightarrow f(x) \leq f(x')$). On peut donc appliquer le théorème 3 sur le treillis ($\mathcal{D}, \leq$) et la fonction $f(x) = ax \oplus b$. Et ce théorème nous dit plusieurs choses :

— il existe au moins une solution à l'équation $x = ax \oplus b$;

— l'ensemble des solutions forme un treillis complet;

— et donc en particulier, il existe une plus petite solution $s$ qui est la borne inférieure de ce treillis de solutions, de plus

$$ \forall x \in \mathcal{D}, f(x) \leq x \leq s. \qquad (2.19) $$

C'est cette plus petite solution que nous poserons comme la solution à l'équation $x = ax \oplus b$. Ce choix est fait parce qu'elle est unique et elle est la plus fine (on en verra les conséquences dans la modélisation des systèmes dans le chapitre suivant).

### 2.4.2 Caractérisation de la solution minimale de $x = ax \oplus b$

Le théorème de Tarski nous dit qu'il existe un ensemble de solutions à l'équation $x = ax \oplus b$ et que la plus petite d'entre elles est le plus grand minorant de l'ensemble $\{x|ax \oplus b \leq x\}$. Le théorème 4 de l'étoile nous permet de caractériser formellement cette solution grâce à l'opérateur étoile.

**Théorème 4 (Théorème de l'étoile).** La plus petite solution de l'équation $x = ax \oplus b$ est :

$$ x = a^*b \qquad (2.20) $$

$$ \text{où } a^* = \bigoplus_{n \in \mathbb{N}} a^n \text{ (opérateur étoile).} $$

*Démonstration.* On note $f(x) = ax \oplus b$ et l'étoile de $f$ :

$$ f^*(x) = e \oplus f(x) \oplus f(f(x)) \oplus \dots = \bigoplus_{n \in \mathbb{N}} f^n(x). \qquad (2.21) $$

Considérons maintenant tout $x \in \mathcal{D}$ tel que $f(x) \leq x$. $f$ est une fonction isotone donc on a $f(f(x)) \leq f(x) \leq x$ et par induction pour tout $n \in \mathbb{N}$ $f^n(x) \leq x$. Si l'on somme toutes ces inégalités on obtient $\bigoplus_{n \in \mathbb{N}} f^n(x) \leq \bigoplus_{n \in \mathbb{N}} x$ autrement dit :

$$ f^*(x) \leq x. \qquad (2.22) $$

Supposons maintenant que $f^*(x) \leq x$ donc cela signifie $f^*(x) \oplus x = x$. Par définition de $f^*$ (équation (2.21)), $e \oplus f(x) \oplus \bigoplus_{n \geq 2} f^n(x) \oplus x = x$ et donc $f(x) \leq x$. On obtient ainsi l'équivalence suivante :

$$ \forall x \in \mathcal{D}, f^*(x) \leq x \Leftrightarrow f(x) \leq x \qquad (2.23) $$

Le théorème 3 du point fixe nous informe que la plus petite solution de $x = ax \oplus b$ existe et cette solution est le plus grand minorant de l'ensemble $\{x|f(x) \leq x\}$ et donc c'est également le
plus grand minorant de l'ensemble $\{x|f^*(x) \le x\}$. Par définition de $f$ et $f^*$, on a :

$$
\begin{align*}
f^*(x) &= \bigoplus_{n \in \mathbb{N}} f^i(x) \\
&= e \oplus (ax \oplus b) \oplus (a(ax \oplus b) \oplus b) \oplus (a(a(ax \oplus b) \oplus b) \oplus b) \dots \\
&= e \oplus ax \oplus b \oplus a^2 x \oplus ab \oplus b \oplus a^3 x \oplus a^2 b \oplus ab \oplus \dots \\
&= \bigoplus_{n \in \mathbb{N}} a^i x \oplus \bigoplus_{n \in \mathbb{N}} a^i b \\
&= \bigoplus_{n \in \mathbb{N}} a^i (x \oplus b) \\
&= a^*(x \oplus b).
\end{align*}
$$

La plus petite solution de $x = ax \oplus b$ est donc le plus grand minorant de l'ensemble

$$
\{x | a^*(x \oplus b) \leq x\}, \qquad (2.24)
$$

ce plus grand minorant est donc $a^*b$.

<figure><img src="image_2.png" /></figure>

**Corollaire 4.** *Toute solution à l'équation $x = ax \oplus b$ est de la forme :*

$a^*x.$

Démonstration. Dans le preuve précédente, l'équation (2.24) indique que toute solution $x$ est telle que : $a^*x \oplus a^*b \le x$, autrement dit $x = a^*x \oplus a^*b \oplus x = a^0x \oplus a^*x \oplus a^*b = a^*x \oplus a^*b$. Que la solution soit la plus petite ou non elle est bien de la forme $a^*x$.

<figure><img src="image_3.png" /></figure>

2.5 Dioïdes matriciels

2.5.1 Introduction aux dioïdes matriciels

Soit $\mathcal{D}$ un dioïde, on considère $\mathcal{D}^{n \times n}$ l'ensemble des matrices carrées de dimension $n$. Soit
$A = (a_{i,j})_{i,j \in \{1, \dots, n\}}$ et $B = (b_{i,j})_{i,j \in \{1, \dots, n\}}$ deux matrices de $\mathcal{D}^{n \times n}$. On définit l'addition de matrice
par :

$$
A \oplus B = (a_{i,j} \oplus b_{i,j})_{i,j \in \{1, \dots, n\}} \qquad (2.25)
$$

Par exemple si $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ et si $B = \begin{pmatrix} b & c \\ a & a \end{pmatrix}$ alors $A \oplus B = \begin{pmatrix} a \oplus b & b \oplus c \\ c \oplus a & d \oplus a \end{pmatrix}$.

On définit le produit de matrice par :

$$
A \otimes B = (c_{i,j})_{i,j \in \{1, \dots, n\}} \qquad (2.26)
$$

où l'élément $c_{i,j}$ de la matrice est défini par :

$$
c_{i,j} = \bigoplus_{k=1}^{n} a_{i,k} \otimes b_{k,j}. \qquad (2.27)
$$

Soit $\epsilon \in \mathcal{D}^{n \times n}$ la matrice définie par :

$$
\epsilon = \begin{pmatrix} \epsilon & \cdots & \epsilon \\ \vdots & \ddots & \vdots \\ \epsilon & \cdots & \epsilon \end{pmatrix} \tag{2.28}
$$

Soit $\mathbf{e} \in \mathcal{D}^{n \times n}$ la matrice définie par :
$$
\mathbf{e} = \begin{pmatrix}
e & \epsilon & \epsilon & \dots & \epsilon \\
\epsilon & e & \epsilon & \dots & \epsilon \\
\vdots & & & & \vdots \\
\epsilon & \dots & \epsilon & e & \epsilon \\
\epsilon & \dots & \epsilon & \epsilon & e
\end{pmatrix} \tag{2.29}
$$

**Théorème 5** (Dioïde matriciel). *L'ensemble* $\mathcal{D}^{n \times n}$ *des matrices carrées de dimension n sur un dioïde* $\mathcal{D}$ *muni de l'opérateur* $\oplus$ *(2.25) (élément neutre $\epsilon$) *et* $\otimes$ *(2.26) (élément neutre $\mathbf{e}$) *est un dioïde*.

Démonstration.

1. Soit $A$ et $B$ deux matrices de $\mathcal{D}^{n \times n}$. La définition de $A \oplus B$ impose que c'est également une matrice de $\mathcal{D}^{n \times n}$. De plus $A \oplus \epsilon = (a_{i,j} \oplus \epsilon)_{i,j} = (a_{i,j})_{i,j} = A = (\epsilon \oplus a_{i,j})_{i,j} = \epsilon \oplus A$. Enfin $\oplus$ est associative/commutative sur $\mathcal{D}^{n \times n}$ car $\oplus$ est associative/commutative sur $\mathcal{D}$. Conclusion : $(\mathcal{D}^{n \times n}, \oplus)$ est un monoïde commutatif d'élément neutre $\epsilon$.

2. Soit $A$ et $B$ deux matrices de $\mathcal{D}^{n \times n}$. La définition de $A \otimes B$ impose que c'est également une matrice de $\mathcal{D}^{n \times n}$. Soit $\mathbf{e}_{i,j}$, l'élément de $\mathbf{e}$ de ligne $i$ et de colonne $j$. On a $A \otimes \mathbf{e} = (c_{i,j})_{i,j}$ avec

$$
c_{i,j} = \bigoplus_{k=1}^{n} a_{i,k} \otimes \mathbf{e}_{k,j} = \bigoplus_{k=1, k \neq j}^{n} a_{i,k} \otimes \mathbf{e}_{k,j} \oplus a_{i,j} \otimes e = a_{i,j}
$$

ainsi, $A \otimes \mathbf{e} = A$. Le raisonnement est similaire pour $\mathbf{e} \otimes A = A$. Enfin $\otimes$ est associative sur $\mathcal{D}^{n \times n}$ :

$$
(A \otimes B) \otimes C = ((a_{i,j})_{i,j} \otimes (b_{i,j})_{i,j}) \otimes (c_{i,j})_{i,j} \quad (2.30)
$$

$$
= \left( \bigoplus_{k=1}^{n} a_{i,k} \otimes b_{k,j} \right)_{i,j} \otimes (c_{i,j})_{i,j} \qquad (2.31)
$$

$$
= \left( \bigoplus_{k'=1}^{n} \left( \bigoplus_{k=1}^{n} a_{i,k} \otimes b_{k,k'} \right) \otimes c_{k',j} \right)_{i,j} \quad (2.32)
$$

$$
= \left( \bigoplus_{k=1}^{n} a_{i,k} \otimes \left( \bigoplus_{k'=1}^{n} b_{k,k'} \otimes c_{k',j} \right) \right)_{i,j} \quad (2.33)
$$

$$
= (a_{i,j})_{i,j} \otimes \left( \bigoplus_{k'=1}^{n} b_{k,k'} \otimes c_{k',j} \right)_{i,j} \quad (2.34)
$$

$$
= A \otimes (B \otimes C) \tag{2.35}
$$

Conclusion : $(\mathcal{D}^{n \times n}, \otimes)$ est un monoïde d'élément neutre $\mathbf{e}$.

3. $\otimes$ est distributif par rapport à $\oplus$, en effet :
$$A \otimes (B \oplus C) = (a_{i,j})_{i,j} \otimes ((b_{i,j})_{i,j} \oplus (c_{i,j})_{i,j}) \quad (2.36)$$

$$= (a_{i,j})_{i,j} \otimes (b_{i,j} \oplus c_{i,j})_{i,j} \quad (2.37)$$

$$= \left(\bigoplus_{k=1}^{n} a_{i,k} \otimes (b_{k,j} \oplus c_{k,j})\right)_{i,j} \quad (2.38)$$

$$= \left(\bigoplus_{k=1}^{n} (a_{i,k} \otimes b_{k,j}) \oplus (a_{i,k} \otimes c_{k,j})\right)_{i,j} \quad (2.39)$$

$$= \left(\bigoplus_{k=1}^{n} (a_{i,k} \otimes b_{k,j}) \oplus \bigoplus_{k=1}^{n} (a_{i,k} \otimes c_{k,j})\right)_{i,j} \quad (2.40)$$

$$= (A \otimes B) \oplus (A \otimes C). \quad (2.41)$$

L'égalité $(A \oplus B) \otimes C = (A \otimes C) \oplus (B \otimes C)$ s'obtient de façon similaire.

4. L'élément neutre $\epsilon$ est absorbant pour le produit, en effet :

$$A \otimes \epsilon = \left(\bigoplus_{k=1}^{n} a_{i,k} \otimes \epsilon\right)_{i,j} = \left(\bigoplus_{k=1}^{n} \epsilon\right)_{i,j} = (\epsilon)_{i,j} = \epsilon \quad (2.42)$$

$$\epsilon \otimes A = \left(\bigoplus_{k=1}^{n} \epsilon \otimes a_{k,j}\right)_{i,j} = \left(\bigoplus_{k=1}^{n} \epsilon\right)_{i,j} = (\epsilon)_{i,j} = \epsilon \quad (2.43)$$

5. La loi $\oplus$ est idempotente, en effet :

$$A \oplus A = (a_{i,j})_{i,j} \oplus (a_{i,j})_{i,j} = (a_{i,j} \oplus a_{i,j})_{i,j} = (a_{i,j})_{i,j} = A \quad (2.44)$$

□

## 2.5.2 Dioïde matriciel complet

**Proposition 4.** Si le dioïde $\mathcal{D}$ est complet alors $\mathcal{D}^{n \times n}$ est complet.

*Démonstration.*

1. La somme de matrices est une somme membre à membre de ces éléments (équation (2.25)). Comme $\mathcal{D}$ est complet toute somme infinie de ces éléments est dans $\mathcal{D}$, ainsi toute somme infinie de matrices est également dans $\mathcal{D}^{n \times n}$.

2. Soit $C = (c_{i,j})_{i,j}$ une matrice de $\mathcal{D}^{n \times n}$ et $A_1 = (a_{1,i_j})_{i,j}, A_2 = (a_{2,i_j})_{i,j}, \dots$ une séquence infinie de matrices de $\mathcal{D}^{n \times n}$ :

$$C \otimes \bigoplus_{\ell=1}^{\infty} A_{\ell} = C \otimes \left( \bigoplus_{\ell=1}^{\infty} a_{\ell_{i_j}} \right)_{i,j} = \left( \bigoplus_{k=1}^{n} c_{i,k} \otimes \bigoplus_{\ell=1}^{\infty} a_{\ell_{k,j}} \right)_{i,j}$$
$\mathcal{D}$ est complet donc :

$$
\begin{align*}
C \otimes \bigoplus_{\ell=1}^{\infty} A_{\ell} &= \left( \bigoplus_{k=1}^{n} \bigoplus_{\ell=1}^{\infty} c_{i,k} \otimes a_{\ell_{k,j}} \right)_{i,j} \\
&= \left( \bigoplus_{\ell=1}^{\infty} \bigoplus_{k=1}^{n} c_{i,k} \otimes a_{\ell_{k,j}} \right)_{i,j} \\
&= \bigoplus_{\ell=1}^{\infty} \left( \bigoplus_{k=1}^{n} c_{i,k} \otimes a_{\ell_{k,j}} \right)_{i,j} \\
&= \bigoplus_{\ell=1}^{\infty} (C \otimes A_{\ell})
\end{align*}
$$

□

2.5.3 Relation d'ordre sur les dioïdes matriciels

Comme dans tout dioïde, la relation d'ordre dans le dioïde matriciel $\mathcal{D}^{n \times n}$ est définie par :

$$
A \leq B \Leftrightarrow A \oplus B = B
$$

Il est à remarquer que si la relation d'ordre sur $\mathcal{D}$ est totale, cela ne signifie pas pour autant
que celle sur $\mathcal{D}^{n \times n}$ est totale, en général la relation est partielle. Pour illustrer ce point, un simple
exemple suffit. Considérons le dioïde complet $\mathbb{R}_{\text{max}}$. Soit les 2 matrices suivantes sur $\mathbb{R}_{\text{max}}^{2 \times 2}$ :

$$
A = \begin{pmatrix} 2 & 3 \\ 7 & 0 \end{pmatrix}, B = \begin{pmatrix} 1 & 4 \\ 2 & 5 \end{pmatrix}
$$

Calculons $A \oplus B$ :

$$
A \oplus B = \begin{pmatrix} \max(2, 1) & \max(3, 4) \\ \max(7, 2) & \max(0, 5) \end{pmatrix} = \begin{pmatrix} 2 & 4 \\ 7 & 5 \end{pmatrix}
$$

Ainsi $A \neq A \oplus B$ et $B \neq A \oplus B$, donc $A$ et $B$ sont incomparables et donc l'ordre $\leq$ sur $\mathbb{R}_{\text{max}}^{2 \times 2}$ n'est que partiel. Pourtant sur $\mathbb{R}_{\text{max}}$, l'ordre est total : pour tous réels $x, y$, soit $x \leq y$ (autrement dit $y = \max(x, y)$), soit $y \leq x$ ($x = \max(x, y)$), aucun couple $x, y$ n'est incomparable.

2.5.4 Caractérisation de la solution minimale de X = AX ⊕ B

Ici on se place dans le contexte où $A$ est une matrice dans un dioïde $\mathcal{D}^{n \times n}$ où $\mathcal{D}$ est un dioïde complet. Comme $\mathcal{D}^{n \times n}$, $X$ et $B$ sont donc des vecteurs colonnes de $\mathcal{D}^n$

$$
X = AX \oplus B \tag{2.45}
$$

Afin de résoudre cette équation, on veut pouvoir exploiter le théorème de l'étoile 4 sur le
dioïde complet $\mathcal{D}^{n \times n}$, mais pour cela, il nous faudrait que $X$ et $B$ soient également des matrices
de $\mathcal{D}^{n \times n}$ or ce n'est pas la cas. Mais nous allons les étendre afin de rentrer dans le cadre du
théorème de l'étoile. On définit :

$$
X_{\mathcal{D}} = \begin{pmatrix} x_1 & \varepsilon & \dots & \varepsilon \\ \vdots & \vdots & & \vdots \\ x_n & \varepsilon & \dots & \varepsilon \end{pmatrix}, B_{\mathcal{D}} = \begin{pmatrix} b_1 & \varepsilon & \dots & \varepsilon \\ \vdots & \vdots & & \vdots \\ b_n & \varepsilon & \dots & \varepsilon \end{pmatrix}
$$
Le théorème de l'étoile nous dit alors que la plus petite solution de $X_D = AX_D \oplus B_D$ est $A^*B_D$. Le vecteur $X$ étant la première colonne de $X_D$ sa plus petite solution est donc la première colonne de $A^*B_D$, et donc au final, la plus petite solution de $X = AX \oplus B$ est

$$X = A^*B \tag{2.46}$$

### 2.5.5 Calcul effectif de $A^*$ quand $A$ est décomposable

Reprenons un instant la définition de l'opérateur $*$ et appliquons-le sur une matrice $A \in \mathcal{D}^{n \times n}$, on a :

$$A^* = \bigoplus_{i=0}^{\infty} A^i = e \oplus A \oplus A^2 \oplus \dots$$

Le problème de cette définition est qu'elle n'est pas très effective. Il est possible d'obtenir $A^*$ en décomposant la matrice en blocs de dimension plus petite et de calculer chaque bloc séparément si une telle décomposition existe.

**Lemme 1.** Soit $A$ une matrice décomposable en 4 matrices carrées $B, C, D, E$ on a :

$$A^* = \begin{pmatrix} B & C \\ D & E \end{pmatrix} = \begin{pmatrix} B^* \oplus B^*C(DB^*C \oplus E)^*DB^* & B^*C(DB^*C \oplus E)^* \\ (DB^*C \oplus E)^*DB^* & (DB^*C \oplus E)^* \end{pmatrix} \tag{2.47}$$

*Démonstration.* Soit $X \in \mathcal{D}^{n \times n}$, une matrice que l'on décompose en 4 blocs :

$$X = \begin{pmatrix} X_{11} & X_{12} \\ X_{21} & X_{22} \end{pmatrix}$$

Le théorème de l'étoile (théorème 4) appliqué aux matrices nous dit que $A^*$ est la plus petite solution de $X = AX + e$ (en effet $A^* = A^*e$).<fnref n="2" />

On obtient ainsi :

$$X_{11} = B X_{11} \oplus C X_{21} \oplus e \tag{2.48}$$

$$X_{12} = B X_{12} \oplus C X_{22} \oplus \epsilon = B X_{12} \oplus C X_{22} \tag{2.49}$$

$$X_{21} = D X_{11} \oplus E X_{21} \oplus \epsilon = D X_{11} \oplus E X_{21} \tag{2.50}$$

$$X_{22} = D X_{12} \oplus E X_{22} \oplus e \tag{2.51}$$

1. Démontrons que $X_{22} = (DB^*C \oplus E)^*$.

En appliquant le théorème de l'étoile dans (2.49), on obtient :

$$X_{12} = B^*C X_{22} \tag{2.52}$$

En substituant dans (2.51), on obtient :

$$X_{22} = D B^* C X_{22} \oplus E X_{22} \oplus e = (D B^* C \oplus E) X_{22} \oplus e \tag{2.53}$$

En appliquant le théorème de l'étoile sur (2.53), on obtient alors :

$$X_{22} = (DB^*C \oplus E)^*e = (DB^*C \oplus E)^* \tag{2.54}$$

<footnote n="2">2. Dans cette démonstration, $e$ et $\epsilon$ dénoteront les éléments neutres peu importe la dimension du dioïde matriciel en support.</footnote>
2. Démontrons que $X_{12} = BC^*(DB^*C \oplus E)^*$.

Pour cela, il suffit de reprendre (2.52) et (2.54), on en déduit immédiatement le résultat :

$$X_{12} = BC^*(DB^*C \oplus E)^* \qquad (2.55)$$

3. Démontrons que $X_{21} = (DB^*C \oplus E)^*DB^*$.

En appliquant le théorème de l'étoile dans (2.48), on obtient :

$$X_{11} = B^*(CX_{21} \oplus e) = B^*CX_{21} \oplus B^* \qquad (2.56)$$

En substituant dans (2.50), on obtient :

$$X_{21} = D(B^*CX_{21} \oplus B^*) \oplus EX_{21} = (DB^*C \oplus E)X_{21} \oplus DB^* \qquad (2.57)$$

En appliquant le théorème de l'étoile sur (2.57), on obtient alors :

$$X_{21} = (DB^*C \oplus E)^*DB^* \qquad (2.58)$$

4. Démontrons que $X_{11} = B^* \oplus B^*C(DB^*C \oplus E)^*DB^*$.

Enfin, à partir de (2.58) et de (2.56), on en déduit immédiatement que :

$$X_{11} = B^*C((DB^*C \oplus E)^*DB^*) \oplus B^* \qquad (2.59)$$

□

La technique issue de ce lemme ne fonctionne que si une décomposition de ce type est possible. Il existe un algorithme de calcul de complexité $n^3$ qui fonctionne dans tous les cas, l'algorithme de Gauss-Seidel généralisé [GM84].
# Chapitre 3

## Modélisations de systèmes à événements discrets sous la forme de Graphe d'Événements Temporisés

Certains systèmes à événements discrets qui mettent en jeu des phénomènes de synchronisation peuvent être décrits de façon linéaire dans l'algèbre des dioïdes. Ces systèmes peuvent également être représentés par un modèle graphique appelé *graphe d'événements temporisé* (GET). Cette représentation découle directement de la théorie des réseaux de Petri. Ce chapitre a pour objectif de présenter les graphes d'événements temporisés et d'en exploiter des modélisations sous une forme algébrique (max, +).

### 3.1 Graphe d'événements temporisé

#### 3.1.1 Définition d'un graphe d'événements temporisé

Les graphes d'événements temporisé sont une classe spécifique de réseau de Petri temporisé. Nous ne présentons ici que la définition de ces graphes et non pas une définition générale de réseau de Petri.

**Définition 10** (Graphe d'événements temporisé (GET)). *Un graphe d'événements temporisés est un quadruplet ($\mathcal{P}$, $\mathcal{T}$, $\mathcal{A}$, $d$) tel que :*

- $\mathcal{P}$ est un ensemble fini de places;

- $\mathcal{T}$ est un ensemble fini de transitions;

- $\mathcal{A} \subseteq \mathcal{P} \times \mathcal{T} \cup \mathcal{T} \times \mathcal{P}$ est un ensemble fini d'arcs;

- pour toute place $p \in \mathcal{P}$,

- il existe toujours un et un seul arc entrant $|(t, p) \in \mathcal{A}| = 1$;

- il existe toujours un et un seul arc sortant $|(p, t) \in \mathcal{A}| = 1$;

- $d: \mathcal{P} \to \mathbb{R}^+$ (ou $d: \mathcal{P} \to \mathbb{Z}^+$) est la durée d'attente dans une place.

Un GET est donc un réseau de Petri avec deux spécificités :

1. chaque place $p$ est associée avec une durée $d(p)$;

2. toute place $p$ est nécessairement associée à une transition entrante (son *preset* $pre(p) = \{t \in \mathcal{T}, (t, p) \in \mathcal{A}\}$ ne contient qu'une transition) et une transition sortante (son *postset* $post(p) = \{t \in \mathcal{T}, (p, t) \in \mathcal{A}\}$ ne contient également qu'une transition).

Comme tout réseau de Petri, un GET est associé à un marquage : $M: \mathcal{P} \to \mathbb{N}$. Le marquage $M(p)$ dénote le nombre de jetons qui est contenu dans la place $p$ à un instant donné. Parmi les transitions, on distingue :

- les *transitions d'entrée* : ces transitions $t$ n'ont pas de places en amont $pre(t) = \{p \in \mathcal{P}, (p, t) \in \mathcal{A}\} = \emptyset$;
- les *transitions de sortie* : ces transitions $t$ n'ont pas de places en aval $post(t) = \{p \in \mathcal{P}, (t,p) \in A\} = \emptyset$;

- les *transitions internes* : ce sont les transitions $t$ qui ne sont ni d'entrée, ni de sortie, autrement dit $pre(t) \neq \emptyset$ et $post(t) \neq \emptyset$.

<figure><img src="image_4.png" /><figcaption>FIGURE 3.1 – Exemple d'atelier d'assemblage à 2 entrées et une sortie (3 machines).</figcaption></figure>

La figure 3.1 illustre le GET d'un atelier d'assemblage. Ce GET est composé de deux transitions d'entrée, une transition de sortie et de six transitions internes. Il caractérise deux lignes de productions (production sur la machine $M_1$ à partir de l'entrée $u_1$ et production sur la machine $M_2$ à partir de l'entrée $u_2$) qui se synchronisent en vue de l'assemblage par la machine $M_3$ du produit final sur la sortie $y$. Les places pour lesquelles les durées ne sont pas affichées ont une durée d'attente nulle. Les places entre les machines représentent les durées de transport des produits entre les machines. Les machines $M_1$ et $M_3$ mettent deux unités de temps pour produire un élément alors que la machine $M_2$ en demande 5. Les machines $M_1$ et $M_2$ peuvent produire un seul élément en même temps alors que la machine $M_3$ peut en produire 3 en parallèle. Commander un tel système consiste à établir une stratégie de production des événements d'entrées (tirs des transitions $u_1$ et $u_2$) afin que la ligne d'assemblage puisse répondre à une certaine consigne en sortie $y$. Un tel GET n'est pas autonome car il dépend du tir des transitions d'entrées $u_1, u_2$.

<figure><img src="image_5.png" /><figcaption>FIGURE 3.2 – Exemple d'un système de transport ferroviaire à deux gares, deux trains et deux bus.</figcaption></figure>

On dit ainsi qu'un GET est *autonome* s'il n'a pas de transitions d'entrée, c'est par exemple le cas du GET représenté sur la figure 3.2. Il représente un système ferroviaire composé de deux gares, deux trains et deux bus. Les gares sont ici représentées par les transitions $x_1$ et $x_2$. Une place représente un trajet entre deux gares et sa durée effective. Chaque jeton représente un train ou un bus. Les deux trains circulent entre les deux gares $x_1$ et $x_2$, le trajet entre $x_1$ et $x_2$ étant plus rapide que celui entre $x_2$ et $x_1$. Les deux bus sont en charge de faire une tournée pour
récupérer des passagers à chaque gare. Un train en gare ne peut partir que si le bus est arrivé et
réciproquement, autrement dit le départ de chaque bus est synchronisé avec le départ de chaque train.

3.1.2 Sémantique de la règle de tir d'un GET : franchissement au plus tôt

Comme tous les réseaux de Petri, un GET modélise le comportement d'un système à événements discrets par la façon dont les transitions du GET sont tirées pour un marquage donné M. Pour qu'une transition soit *tirable*, il faut tout d'abord qu'elle soit *sensibilisée* et pour qu'une transition soit sensibilisée il faut que toute place en amont de cette transition sensibilise cette transition.

Dans le cas des réseaux de Petri simples (réseaux sans poids associés aux arcs), une place sensibilise une transition dès lors que la place est marquée (présence d'un jeton). Dans le cas d'un GET, ce n'est pas le cas, la sensibilisation dépend en plus d'une contrainte temporelle.

Règle de sensibilisation : *Un jeton dans une place *p* ne sensibilise la transition sortante que s'il est resté dans la place pour une durée minimale *d(p)*. Dans le cas particulier où le jeton est présent à l'origine des temps, cette durée est nulle.*

Plus formellement, on distingue deux cas :

1. Cas général, la place *p* reçoit un jeton au temps *t* > 0, la transition sortante est sensibilisée par ce jeton au temps *t* + *d(p)*

2. Cas initial, tout jeton présent dans *p* dans le marquage initial (*t* = 0) sensibilise immédiatement la transition (*t* = 0).

Revenons encore un instant sur les réseaux de Petri classiques. Une fois la transition sensi-
bilisée par toutes les places en amont, la transition est dite *tirable* mais elle n'est pas pour autant
tirée à cet instant, elle peut être tirée à tout instant après sa sensibilisation (ou parfois elle n'est
même pas tirée). Là encore, la règle de tir d'un GET est spécifique :

**Règle de tir (franchissement au plus tôt)** Une transition sensibilisée par toutes ses places amont à la date *t* est tirée à la date *t*.

Pour qu'une transition soit sensibilisée à l'instant *t*, il faut que toutes les places de *pre(t)* sensibilisent cette transition à cet instant, autrement dit la date de tir de la transition correspond exactement à la date de sensibilisation de la dernière place à devoir sensibiliser *t*. Cette règle de tir (franchissement au plus tôt) caractérise la notion de *synchronisation*.

**Exemples** : Reprenant l'exemple de la figure 3.1, le marquage initial est tel que le système est bloqué. Pour démarrer, il faut au moins un tir de transition de $u_1$ ou $u_2$. Supposons qu'un tir de $u_1$ ait lieu à la date 1. Un jeton est ainsi placé à la date 1 dans la place qui succède $u_1$. Ce jeton va donc sensibiliser la transition $x_1$ à la date 2. L'autre place de $pre(x_1)$ sensibilisant $x_1$ depuis la date 0, cela signifie que $x_1$ est sensibilisée par toutes les places de $pre(x_1)$ à la date 2. La sémantique du franchissement au plus tôt impose alors que $x_1$ est nécessairement tirée à la date 2. De même, la transition $x_2$ sera nécessairement tirée à la date 2+2=4.

Dans l'exemple du système autonome de la figure ??, à la date 0, on considère que les durées
effectives des places sont nulles. Ainsi, selon le marquage initial présenté sur la figure, les deux
bus vont partir tous les deux à la date 0. Le train représenté par le jeton dans la place entre
$x_1$ et $x_2$ débutera son trajet entre $x_2$ et $x_1$ également à la date 0 (d'une durée de 8ut). Le train
représenté par le jeton dans la place entre $x_2$ et $x_1$ débutera son trajet entre $x_1$ et $x_2$ également à
la date 0 (d'une durée de 2ut). Le bus revient en $x_1$ après 1ut et doit attendre le train en partance
de $x_2$ pour $x_1$ qui arrivera à la date 8. Le bus repartira de $x_1$ à la date 8 de même que le train en
partance pour $x_2$.
## 3.2 Mise en équations algébriques

Un GET est défini sous la forme d'un langage graphique très pratique pour la modélisation de systèmes temporisés qui nécessitent des synchronisations. Cette section a pour objectif de montrer comment on peut représenter ces GET sous formes algébriques et comment exploiter cette représentation. La mise en équation algébrique d'un GET repose sur le principe suivant. Le tir d'une transition $x \in T$ dans le GET correspond à l'occurrence d'un événement de type $x$ à une certaine date. Le comportement de cette transition est donc parfaitement caractérisé par l'ensemble de ces événements datés de type $x$. Et le comportement du GET est parfaitement caractérisé par l'ensemble des événements datés associés à chacune de ses transitions. Nous limiterons l'étude au cas où les places des GET ont des durées dans $\mathbb{Z}$ mais la théorie détaillée s'étend facilement à des durées réelles (seule la mise en œuvre informatique est plus complexe avec les erreurs d'arrondis inhérentes à $\mathbb{R}$, dans $\mathbb{Z}$ les calculs numériques étant toujours certains). Nous ferons également l'hypothèse que tout tir d'une transition d'entrée d'un GET s'effectue sur un tick d'horloge et donc que sa date de tir est également dans $\mathbb{Z}$.

### 3.2.1 Compter les événements avec des dateurs

Cette section présente la mise en équations aux dateurs. Soit $x \in T$, une transition quelconque du GET, on va lui associer une fonction dateur qui, pour des soucis de simplicité dans les notations, portera le même nom que la transition $x$.<fnref n="1" /> On suppose que le système démarre à la date $d_{init}$ (et nous supposerons dans la suite que $d_{init} = 0$) et que les jetons du marquage initial sont présents depuis l'instant $-\infty$.

**Définition 11 (Dateur).** Le dateur de la transition $x$ d'un GET est la fonction :

$$x: \mathbb{Z} \to \mathbb{Z}_{max}$$

qui associe au $k + 1$<sup>ème</sup> tir de la transition, la date $x(k)$ de ce tir de transition.

On numérote l'occurrence des événements à partir de 0 (l'événement 0 est associé au premier tir de la transition). Revenons sur l'exemple de la figure 3.1. Dans le scénario où on a un premier tir de $u_1$ à la date 1, puis un autre à la date 2 et finalement deux tirs instantanés de $u_1$ à la date 5, ce scénario est associé au dateur $u_1(k)$ suivant :

$$u_1(0) = 1, u_1(1) = 2, u_1(2) = 5, u_1(3) = 5.$$

Une fonction dateur peut se représenter graphiquement par un ensemble de points sur un plan. La figure 3.3 est par exemple la représentation graphique du dateur $u_1(k)$ défini ci-dessus.

Une fonction dateur renvoie une valeur du dioïde $Z_{max}$ (dioïde $(\mathbb{Z}, \max, +)$), elle peut donc servir à mettre en équation les contraintes temporelles entre les tirs de transition d'un GET. Par exemple, sur la figure 3.1, l'occurrence d'événement $k$ de $x_2$ est conditionnée par celle de $x_1$ qui doit se produire 2ut avant, on a donc :

$$x_2(k) = x_1(k) + 2.$$

L'occurrence $k$ de $x_1$ est conditionnée par celle de $u_1$ et l'occurrence $k-1$ de $x_2$, cette occurrence aura lieu à la date la plus récente entre celle de $x_1$ suivie d'un délai de 1 et celle de $x_2$, d'où :

$$x_1(k) = \max(u_1(k) + 1, x_2(k - 1)).$$

Si l'on reprend maintenant les notations $\oplus = \max$ et $\otimes = +$ sur $Z_{max}$ les deux expressions précédentes peuvent s'écrire :

<footnote n="1">1. La notation $x$ sera sans ambiguïté dans le contexte où elle sera employée.</footnote>
<figure><img src="image_6.png" /><figcaption>FIGURE 3.3 – Représentation graphique du dateur $u_1 : u_1(0) = 1, u_1(1) = 2, u_1(2) = 5, u_1(3) = 5$</figcaption></figure>

$$ 
\begin{aligned}
x_2(k) &= 2 \otimes x_1(k) \\
x_1(k) &= (1 \otimes u_1(k)) \oplus (0 \otimes x_2(k-1)) \\
&= (1 \otimes u_1(k)) \oplus (e \otimes x_2(k-1)) \\
&= (1 \otimes u_1(k)) \oplus x_2(k-1)
\end{aligned}
$$

Ainsi, on peut écrire l'ensemble des équations aux dateurs du GET de la figure 3.1.

$$ 
\begin{aligned}
x_1(k) &= (1 \otimes u_1(k)) \oplus x_2(k-1) \\
x_2(k) &= 2 \otimes x_1(k) \\
x_3(k) &= (2 \otimes u_2(k)) \oplus x_4(k-1) \\
x_4(k) &= 5 \otimes x_3(k) \\
x_5(k) &= (1 \otimes x_2(k)) \oplus (3 \otimes x_4(k)) \oplus x_6(k-3) \\
x_6(k) &= 2 \otimes x_5(k) \\
y(k) &= x_6(k)
\end{aligned}
$$

Introduisons maintenant un vecteur d'entrepôt, un vecteur d'états et un vecteur de sortie :

$$ u(k) = \begin{bmatrix} x_1(k) \\ x_2(k) \end{bmatrix}, x(k) = \begin{bmatrix} x_1(k) \\ x_2(k) \\ x_3(k) \\ x_4(k) \\ x_5(k) \\ x_6(k) \end{bmatrix}, y(k) = \begin{bmatrix} y(k) \end{bmatrix} $$

Le système d'équations précédent peut alors se réécrire sous la forme matricielle suivante :
$$
\begin{align*}
x(k) &= \begin{bmatrix} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ 2 & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & 5 & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 3 & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & 2 \end{bmatrix} x(k) \oplus \begin{bmatrix} \varepsilon & 0 & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \end{bmatrix} x(k-1) \\
&\quad \oplus \varepsilon x(k-2) \oplus \begin{bmatrix} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & 0 \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \end{bmatrix} x(k-3) \oplus \begin{bmatrix} 1 & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & 2 \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \end{bmatrix} u(k)
\end{align*}
$$

$$
y(k) = [\varepsilon \quad \varepsilon \quad \varepsilon \quad \varepsilon \quad \varepsilon \quad 0] x(k)
$$

D'une manière générale, on obtient donc la forme suivante :

$$
x(k) = \bigoplus_{i=0}^{p} A_i x(k-i) \oplus \bigoplus_{j=0}^{q} B_j u(k-j) \quad (3.1)
$$

$$
y(k) = \bigoplus_{l=0}^{r} C_l x(k-l) \qquad (3.2)
$$

En procédant à une extension de l'état $x$, il est possible de ramener le système d'équations
précédent à un système où le retard est au plus de 1 sur le vecteur d'états et de 0 sur le vecteur
d'entrées. Supposons par exemple que la composante $x_i(k)$ de $x(k)$ dépend de $x_j(k-r)$, $r > 1$ :

$$
x_i(k) = \dots \oplus (d \otimes x_j(k-r)) \oplus \dots
$$

Étendons le vecteur $x$ avec :

$$
\begin{bmatrix}
x_{i,-1} \\
\vdots \\
x_{i,-(r-1)}
\end{bmatrix}
$$

et remplaçons l'équation précédente par le système d'équations suivant :

$$
x_i(k) = \dots \oplus x_{i,-1}(k-1) \oplus \dots \tag{3.3}
$$

$$
x_{i,-1}(k) = x_{i,-2}(k-1) \tag{3.4}
$$

$$
\dots \tag{3.5}
$$

$$
x_{i,-(r-1)}(k) = d \otimes x_j(k-1) \tag{3.6}
$$

Par définition, cette extension est équivalente au système initial :

$$
x_i(k) = \dots \oplus x_{i,-1}(k-1) \oplus \dots \tag{3.7}
$$

$$
= \dots \oplus x_{i,-2}(k-2) \oplus \dots \tag{3.8}
$$

$$
\dots \tag{3.9}
$$

$$
= \dots \oplus x_{i,-(r-1)}(k-(r-1)) \oplus \dots \tag{3.10}
$$

$$
= \dots \oplus (d \otimes x_j(k-r)) \oplus \dots \tag{3.11}
$$

En pratique, cette extension du vecteur d'états peut se faire sur le GET par une extension
evénementielle. La figure 3.4 illustre le principe général d'une telle extension dans les trois cas
possibles. Le premier cas est celui d'un retard de $r > 1$ jetons entre deux transitions internes $x_i(k) = \cdots \oplus (d \otimes x_j(k-r)) \oplus \cdots$ comme présenté ci-dessus. Graphiquement, il consiste à remplacer la place entre $x_j$ et $x_i$ contenant $r$ jetons par une chaîne de $r$ places/$r-1$ transitions, chaque place ne contenant qu'un jeton. Seule la première place est associée au délai $d$, les autres ont un délai nul. Le deuxième cas est celui d'un retard $r \ge 1$ entre une transition d'entrée $u_j$ et une transition interne $x_i$ ($x_i(k) = \cdots \oplus (d \otimes u_j(k-r)) \oplus \cdots$). On veut pouvoir exprimer des équations en fonction d'une entrée sans retard. Dans ce deuxième cas, on remplace la place entre $u_j$ et $x_i$ contenant $r$ jetons par une chaîne de $r+1$ places/$r$ transitions : la première place porte le délai $d$ mais ne contient aucun jeton (pas de retard sur l'entrée donc), les autres places ont un jeton et un délai associé nul. Enfin le troisième cas implique une transition interne $x_j$ et une sortie $y_i$ et un retard $r \ge 1$ où l'on veut pouvoir exprimer la sortie $y_i$ sans retard. Dans ce troisième cas, on remplace la place entre $x_j$ et $y_i$ contenant $r$ jetons par une chaîne de $r+1$ places/$r$ transitions : la première place porte le délai $d$ et un jeton, les autres places ont un délai associé nul. Elles ont également toutes un jeton sauf la dernière.

<figure><img src="image_7.png" /><figcaption>FIGURE 3.4 – Principe général de remplacement d'une place dont le marquage initial est de $r$ jetons par une extension événementielle dans un GET.</figcaption></figure>

Au final, en appliquant ces trois types d'extensions pour chaque retard dans le système d'équations, ce système peut se ramener à la forme suivante :

$$x(k) = \bar{A}_0 x(k) \oplus \bar{A}_1(k-1) \oplus \bar{B}_0 u(k) \quad (3.12)$$

$$y(k) = \bar{C}_0 x(k) \quad (3.13)$$

L'équation (3.12) est implicite puisque $x(k)$ apparaît dans les deux membres. La règle de tir du GET étant un franchissement au plus tôt, nous recherchons la solution $x(k)$ la plus rapide, autrement dit la solution la plus petite dans $Z_{max}$. Ainsi, on peut appliquer le théorème de l'étoile afin de rendre (3.12) explicite :

$$x(k) = \bar{A}_0^* (\bar{A}_1 x(k-1) \oplus \bar{B}_0 u(k)) \quad (3.14)$$

$$= \bar{A}_0^* \bar{A}_1 x(k-1) \oplus \bar{A}_0^* \bar{B}_0 u(k) \quad (3.15)$$

Revenons à notre exemple, c'est l'équation de $x_5(k)$ qui nécessite un retard de 3ut (c.-à-d. $x_6(k-3)$). On étend donc le vecteur d'états avec deux nouvelles variables $x_7$ et $x_8$ et on remplace
$$x_5(k) = (1 \otimes x_2(k)) \oplus (3 \otimes x_4(k)) \oplus x_6(k-3)$$

par le système

$$x_5(k) = (1 \otimes x_2(k)) \oplus (3 \otimes x_4(k)) \oplus x_8(k-1) \quad (3.16)$$

$$x_8(k) = x_7(k-1) \quad (3.17)$$

$$x_7(k) = x_6(k-1) \quad (3.18)$$

Sous forme matricielle, on a ainsi :

$$x(k) = \begin{bmatrix} x_1(k) \\ x_2(k) \\ x_3(k) \\ x_4(k) \\ x_5(k) \\ x_6(k) \\ x_7(k) \\ x_8(k) \end{bmatrix} = \begin{bmatrix} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ 2 & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & 5 & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & 1 & \varepsilon & 3 & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & 2 & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \end{bmatrix} x(k) \oplus \begin{bmatrix} \varepsilon & 0 & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & 0 \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \end{bmatrix} x(k-1) \oplus \begin{bmatrix} 1 & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & 2 \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \end{bmatrix} u(k) \\ = \bar{A}_0 x(k) \oplus \bar{A}_1 x(k-1) \oplus \bar{B}_0 u(k)$$

Afin d'obtenir finalement la représentation d'états on calcule $\bar{A}_0^* \bar{A}_1$ et $\bar{A}_0^* \bar{B}_0$.

$$\vec{A}_0 = \begin{bmatrix} 0 & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ 2 & 0 & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & 0 & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & 5 & 0 & \varepsilon & \varepsilon & \varepsilon \\ 3 & 1 & 8 & 3 & 0 & \varepsilon & \varepsilon \\ 5 & 3 & 10 & 5 & 2 & 0 & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & 0 \end{bmatrix}, \quad \vec{A}_0^* \bar{A}_1 = \begin{bmatrix} \varepsilon & 0 & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & 2 & \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 5 & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & 3 & \varepsilon & 8 & \varepsilon & \varepsilon & 0 \\ \varepsilon & 5 & \varepsilon & 10 & \varepsilon & \varepsilon & 2 \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon \end{bmatrix}, \quad \vec{A}_0^* \bar{B}_0 = \begin{bmatrix} 1 & \varepsilon \\ 3 & \varepsilon \\ \varepsilon & 2 \\ \varepsilon & 7 \\ 4 & 10 \\ 6 & 12 \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \end{bmatrix}$$

La figure 3.5 présente la représentation graphique de l'extension événementielle qui a été définie dans cet exemple. La place suivant $x_6$ et précédant $x_5$ et contenant 3 jetons (le fameux retard de 3) a été remplacée par une séquence de 3 places avec un jeton et de deux transitions $x_7$ et $x_8$ entre ces places.

### 3.2.2 Mesurer le temps avec des compteurs

Les dateurs sont des fonctions qui associent à un numéro d'événement la date de son occurrence. Une autre façon de caractériser le comportement d'un GET est de compter le nombre d'occurrences d'un événement qui ont eu lieu avant une certaine date. Comme pour le dateur de la transition $x$, le compteur de la transition $x$ sera également noté $x$.

**Définition 12 (Compteur).** Le compteur de la transition $x$ d'un GET est la fonction :

$$x : \mathbb{Z} \to \mathbb{Z}_{min}$$

qui associe à la date $t \in \mathbb{Z}$ le nombre $x(t)$ de tirs de la transition $x$ qui ont eu lieu à toute date $t' \le t$.
<figure><img src="image_8.png" /><figcaption>FIGURE 3.5 – Extension du GET 3.1 remplaçant le retard de 3 entre $x_5$ et $x_6$ par une séquence de 3 retards de 1.</figcaption></figure>

Le domaine temporel est $\mathbb{Z}$. Si l'on suppose que le système démarre à la date $d_{init} = 0$, on impose donc que $\forall t < 0, x(t) = 0$. Revenons maintenant sur l'exemple de la figure 3.1 et notre premier scénario où on a un premier tir de $u_1$ à la date 1, puis un autre à la date 2 et finalement deux tirs instantanés de $u_1$ à la date 5, ce scénario est associé au compteur $u_1(t)$ suivant :

$$u_1(0) = 0, u_1(1) = 1, u_1(2) = 2, u_1(3) = 2, u_1(4) = 2, u_1(5) = 4.$$

Alors qu'un dateur retourne une valeur sur le dioïde $\mathbb{Z}_{max}$, un compteur retourne une valeur sur le dioïde $\mathbb{Z}_{min}$ et on va comprendre pourquoi et mettant en équation le GET de la figure 3.1 avec les compteurs.

Tout tir de $x_2$ est causé par le tir de $x_1$ avec un retard de 2, donc à tout instant le nombre de tirs de $x_2$ est le nombre de tirs de $x_1$ à $t-2$ :

$$x_2(t) = x_1(t - 2)$$

La transition $x_1$ n'est tirée que si :

1. elle est sensibilisée par un jeton dans la place entre $u_1$ et $x_1$ qui est resté une unité de temps,

2. et elle est sensibilisée par un jeton dans la place entre $x_2$ et $x_1$.

Au temps $t$, le nombre de fois où la place entre $u_1$ et $x_1$ a pu être sensibilisée pour un tir potentiel de $x_1$ avant ou à la date $t$ est le nombre de tirs de $u_1$ avant ou à la date $t-1$, soit donc $u_1(t-1)$. De même, le nombre de fois où la place entre $x_2$ et $x_1$ a pu être sensibilisée pour un tir potentiel de $x_1$ avant ou à la date $t$ est le nombre de tirs de $x_2$ avant ou à la date $t$ augmenté de 1 (car il y a déjà un jeton dans le marquage initial qui sensibilise $x_1$ à la date 0), c'est donc $1+x_2(t)$. Sachant que le tir de $x_1$ nécessite les deux conditions de sensibilisation et que la sémantique de tir est celle du franchissement au plus tôt, le nombre de tirs de $x_1$ avant ou à la date $t$ est donc le minimum du nombre de sensibilisations de ces deux places, ainsi :

$$x_1(t) = \min(u_1(t-1), 1 + x_2(t))$$

Comme nous l'avons fait pour les dateurs, on peut reprendre ces deux équations en exploitant les opérateurs $\oplus = \min$ et $\otimes = +$ du dioïde $\mathbb{Z}_{min}$, on a ainsi :

$$x_2(t) = x_1(t - 2)$$

$$x_1(t) = u_1(t - 1) \oplus (1 \otimes x_2(t))$$
On peut ainsi écrire l'ensemble des équations aux compteurs du GET de la figure 3.1.

$$x_1(t) = u_1(t - 1) \oplus (1 \otimes x_2(t))$$

$$x_2(t) = x_1(t - 2)$$

$$x_3(t) = u_2(t - 2) \oplus (1 \otimes x_4(t))$$

$$x_4(t) = x_3(t - 5)$$

$$x_5(t) = x_2(t - 1) \oplus x_4(t - 3) \oplus (3 \otimes x_6(t))$$

$$x_6(t) = x_5(t - 2)$$

$$y(t) = x_6(t)$$

Sous forme matricielle, on obtient :

$$x(t) = \begin{bmatrix} \varepsilon & 1 & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 1 & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & 3 \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \end{bmatrix} x(t) \oplus \varepsilon x(t-1) \oplus \begin{bmatrix} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ 0 & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon \end{bmatrix} x(t-2)$$

$$\oplus \begin{bmatrix} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & 0 & \varepsilon \end{bmatrix} x(t-3) \oplus \varepsilon x(t-4) \oplus \begin{bmatrix} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \end{bmatrix} x(t-5)$$

$$\oplus \varepsilon u(t) \oplus \begin{bmatrix} 0 & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \end{bmatrix} u(t-1) \oplus \begin{bmatrix} \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \\ \varepsilon & 0 \\ \varepsilon & \varepsilon \\ \varepsilon & \varepsilon \end{bmatrix} u(t-2)$$

$$y(t) = [\varepsilon \quad \varepsilon \quad \varepsilon \quad \varepsilon \quad \varepsilon \quad 0] x(t)$$

Ainsi, la mise en équations aux compteurs a la forme générale suivante :

$$x(t) = \bigoplus_{i=0}^{p} A_i x(t-i) \oplus \bigoplus_{j=0}^{q} B_j u(t-j) \qquad (3.19)$$

$$y(t) = \bigoplus_{l=0}^{r} C_l x(t-l) \qquad (3.20)$$

On veut pouvoir réécrire ce système en exprimant des retards au plus de 1. Comme avec les équations aux dateurs, il est possible de ramener le système d'équations précédent à un système où le retard est au plus de 1 (fonction de $x(t)$ et de $x(t-1)$ uniquement) sur le vecteur d'états et de 0 sur le vecteur d'entrées (fonction de $u(t)$ uniquement). Supposons par exemple que la composante $x_i(t)$ de $x(t)$ dépend de $x_j(t-d)$, $d > 1$ :

$$x_i(t) = \dots \oplus (r \otimes x_j(t-d)) \oplus \dots$$
Étendons le vecteur $x$ avec :

$$ \begin{bmatrix} x_{i,-1} \\ \vdots \\ x_{i,-(d-1)} \end{bmatrix} $$

et remplaçons l'équation précédente par le système d'équations suivant :

$$ x_i(t) = \cdots \oplus r \otimes x_{i,-1}(t-1) \oplus \cdots \qquad (3.21) $$

$$ x_{i,-1}(t) = x_{i,-2}(t-1) \qquad (3.22) $$

$$ \dots \qquad (3.23) $$

$$ x_{i,-(d-1)}(t) = x_j(t-1) \qquad (3.24) $$

Par définition, cette extension est équivalente au système initial :

$$ x_i(t) = \cdots \oplus (r \otimes x_{i,-1}(t-1)) \oplus \cdots \qquad (3.25) $$

$$ = \cdots \oplus (r \otimes x_{i,-2}(t-2)) \oplus \cdots \qquad (3.26) $$

$$ \dots \qquad (3.27) $$

$$ = \cdots \oplus (r \otimes x_{i,-(d-1)}(t - (d-1))) \oplus \cdots \qquad (3.28) $$

$$ = \cdots \oplus (r \otimes x_j(t-d)) \oplus \cdots \qquad (3.29) $$

Au final, en appliquant ce type d'extension pour chaque retard supérieur à 1 dans le système d'équations initial, ce système peut se ramener à la forme suivante :

$$ x(t) = \bar{A}_0 x(t) \oplus \bar{A}_1(t-1) \oplus \bar{B}_0 u(t) \qquad (3.30) $$

$$ y(t) = \bar{C}_0 x(t) \qquad (3.31) $$

En pratique, on constate qu'un retard de type $x_j(t-d)$ dans l'équation aux compteurs d'une transition $x_i$ vient de fait qu'il existe une place dans le GET entre $x_j$ et $x_i$ associée à une durée d'attente de $d$. Autrement dit, l'extension du vecteur d'état pour réécrire le système avec un retard de 1, revient graphiquement dans le GET à remplacer chaque place dont la durée associée $d$ est strictement supérieure à 1 par une séquence de $d$ places/$d-1$ transitions dont chaque place est de durée 1 (voir la figure 3.6).

Dans le cas particulier où le retard est sur une entrée ($u_j(t-d)$) avec $d \ge 1$, on veut une expression de l'entrée avec un retard nul, qui nous impose de rajouter une $d + 1^{ème}$ place/ $d^{ème}$ transition entre $u_j$ et la séquence de places/transitions précédentes, $d + 1^{ème}$ place dont la durée associée est nulle. De même dans le cas particulier où le retard est sur une transition interne ($x_j(t-d)$) avec $d \ge 1$ en relation avec une sortie $y_i(t)$, on veut une expression sans retard entre $y_i$ et $x_j$. Elle nous impose de rajouter une $d + 1^{ème}$ place/ $d^{ème}$ transition entre la dernière transition de la séquence de places/transitions précédentes et la transition de sortie, $d + 1^{ème}$ place dont la durée associée est nulle.

Enfin, il suffit maintenant de constater que le système d'équations (3.30) est identique à celui de (3.12) (seul le dioïde change, de $Z_{max}$ pour les dateurs, on est passé à $Z_{min}$ pour les compteurs) et la réprésentation d'états des équations aux compteurs est donc similaire :

$$ x(t) = \bar{A}_0^* \bar{A}_1 x(t-1) \oplus \bar{A}_0^* \bar{B}_0 u(t) \qquad (3.32) $$

$$ y(t) = \bar{C}_0 x(t) \qquad (3.33) $$

Reprenons l'exemple de la figure 3.1. L'extension temporelle entre la transition $u_2$ et la transition $x_3$ remplace la place d'une durée 2 par une chaîne de 3 places/2 transitions ($x_7, x_8$) la première place étant de durée nulle et les deux autres de durée 1. L'extension temporelle entre
<figure><img src="image_9.png" /><figcaption>FIGURE 3.6 – Principe général de remplacement d’une place associée à la durée *d* par une extension temporelle dans un GET.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIGURE 3.7 – Extension temporelle du GET 3.1 remplaçant toutes les durées de places supérieures à 1 et garantissant un retard nul sur les entrées.</figcaption></figure>
$$ \bar{B}_0 = \begin{bmatrix} \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \\ \epsilon & \epsilon \end{bmatrix} $$

$$ \bar{A}_0^* = \begin{bmatrix} 0 & 1 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & 0 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & 0 & 1 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & 0 & 3 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 0 \end{bmatrix} $$
### 3.3.1 Caractérisation de la réponse impulsionnelle

À partir de cette représentation, on peut mettre en évidence une relation d'entrée-sortie :

$$y(k) = Cx(k) \tag{3.36}$$

$$= C(Ax(k-1) \oplus Bu(k)) \tag{3.37}$$

$$= CAx(k-1) \oplus CBu(k) \tag{3.38}$$

$$= CA(Ax(k-2) \oplus Bu(k-1)) \oplus CBu(k) \tag{3.39}$$

$$= CA^2x(k-2) \oplus CABu(k-1) \oplus CBu(k) \tag{3.40}$$

$$= \vdots \tag{3.41}$$

$$= CA^p x(k-p) \oplus \bigoplus_{i=0}^{p-1} CA^i Bu(k-i), \forall p \ge 0 \tag{3.42}$$

Considérons maintenant que $p > k$, que vaudrait le dateur $x(k-p)$ du numéro d'événement négatif $k-p$. On a considéré que les événements sont numérotés à partir de $k=0$ et donc que les événements à numéros négatifs n'existent pas, autrement dit ils ont eu lieu à la date $-\infty$, on a donc sur $\mathbb{Z}_{max}$ :

$$\forall p > k, x(k-p) = \epsilon \tag{3.43}$$

En conséquence, si $p > k$, on peut écrire :

$$y(k) = \bigoplus_{i=0}^{p-1} CA^i B u(k-i), \forall p > k \tag{3.44}$$

La remarque que nous avons fait sur le dateur $x(k-p)$ porte également sur le dateur $u(k-p)$

$$\forall p > k, u(k-p) = \epsilon \tag{3.45}$$

Ainsi on obtient :

$$y(k) = \bigoplus_{i=0}^{k} CA^i B u(k-i) \tag{3.46}$$

On note $H(i)$ la matrice suivante :

$$H(i) = \begin{cases} CA^i B & \text{si } i \ge 0 \\ \epsilon & \text{sinon} \end{cases} \tag{3.47}$$

Il en résulte que :

$$y(k) = \bigoplus_{i \in \mathbb{Z}} H(i)u(k-i) \tag{3.48}$$

Dans l'équation (3.48), la sortie $y(k)$ n'est plus dépendante de l'état du système mais uniquement de son entrée. Cette équation peut être perçue comme la somme des effets des entrées $u$. De ce point de vue, $y(k)$ est le résultat de la k-ième occurrence de l'entrée $u$ (c.-à-d. $H(0)u(k)$) combiné avec la $k-1$-ème occurrence de l'entrée $u$ (c.-à-d. $H(1)u(k-1)$), la $k-2$-ième occurrence de $u$... et ce, jusqu'à l'origine de l'établissement de ces entrées.
Enfin considérons maintenant le vecteur $\mathbf{e}(i)$ compatible en dimension avec le vecteur d'entrée $\mathbf{u}$ du système tel que :

$$ \mathbf{e}(i) = \begin{cases} \mathbf{e} & \text{si } i \ge 0 \\ \epsilon & \text{sinon} \end{cases} \qquad (3.49) $$

$\mathbf{e}(i)$ est donc un vecteur d'entrées dont les composantes sont toutes $\epsilon$ si $i \ge 0$. On rappelle que $\epsilon$ dans $\mathbb{Z}_{max}$ est l'élément du produit de $\mathbb{Z}_{max}$. Si on impose comme entrée au système $\mathbf{u}(k-i) = \mathbf{e}(k-i)$, on obtient :

$$ y(k) = \bigoplus_{i \in \mathbb{Z}} H(i) \mathbf{e}(k-i) = \bigoplus_{i \in \mathbb{Z}} H(i) \qquad (3.50) $$

On appelle le vecteur $\mathbf{e}(i)$ une impulsion. Algébriquement, la présence de l'élément neutre $\epsilon$ caractérise la présence d'un nombre infini d'occurrence d'événements à un instant et le système répond à cette impulsion en produisant $\mathbf{y}(k) = \bigoplus_{i \in \mathbb{Z}} H(i)$. C'est pourquoi $H(i)$ est appelée la réponse impulsionnelle du système, c'est une propriété intrinsèque du système mettant en relation les entrées et les sorties du système mais indépendantes d'entrées $\mathbf{u}$ quelconques.

### 3.3.2 Dioïdes des dateurs et représentation par sup-convolution

La formulation précédente de la relation entrée-sortie n'est pas très élégante, elle définit chaque élément $y(k)$ du dateur $y$ en fonction du dateur $u$. Nous aimerions pouvoir établir une relation entre le dateur $y$ et le dateur $u$. Soit $\mathcal{D}_d$ l'ensemble des fonctions dateurs $\mathbb{Z} \to \mathcal{D}$ (($\mathcal{D}$, $\oplus$, $\otimes$) pouvant être $\mathbb{R}_{max}$, $\mathbb{Z}_{max}$ ...). Soit $d_1, d_2$ deux dateurs de $\mathcal{D}_d$, on peut définir deux opérateurs $\oplus_d$ et $\otimes_d$ sur $\mathcal{D}_d$ comme suit :

— $d_1 \oplus_d d_2$ est le dateur de $\mathcal{D}_d$ tel que :

$$ \forall k \in \mathbb{Z}, (d_1 \oplus_d d_2)(k) = d_1(k) \oplus d_2(k) \qquad (3.51) $$

— $d_1 \otimes_d d_2$ est le dateur de $\mathcal{D}_d$ tel que :

$$ \forall k \in \mathbb{Z}, (d_1 \otimes_d d_2)(k) = \text{Sup}_{s \in \mathbb{Z}}[d_1(k-s) \otimes d_2(s)] = \bigoplus_{s \in \mathbb{Z}} d_1(k-s) \otimes d_2(s) \qquad (3.52) $$

Ainsi $d_1 \oplus_d d_2$ est le dateur somme et $d_1 \otimes_d d_2$ est le dateur obtenu par sup-convolution (équivalent du produit de convolution pour les algèbres (max, +)). On peut alors démonter que ($\mathcal{D}_d$, $\oplus_d$, $\otimes_d$) forme un dioïde où les éléments neutres sont les suivants :

— l'élément neutre $\epsilon_d$ pour $\oplus_d$ est le dateur défini par

$$ \forall k \in \mathbb{Z}, \epsilon_d(k) = -\infty, $$

— l'élément neutre $e_d$ pour $\otimes_d$ est l'impulsion

$$ \forall k < 0, e_d(k) = \epsilon, \forall k \ge 0, e_d(k) = e. $$

Et il en est de même pour le dioïde matriciel $\mathcal{D}_d^{n \times n}$. Maintenant, si l'on reprend l'équation (3.48), on constate que la relation entre $y$ et $u$ est définie par sup-convolution, elle peut se réécrire dans $\mathcal{D}_d^{n \times n}$ :

$$ y = H \otimes_d u = H u = CA^*B u \qquad (3.53) $$

De même, l'équation (3.50) de la réponse impulsionnelle peut se réécrire :

$$ H \mathbf{e}_d = H \otimes_d \mathbf{e}_d = H. \qquad (3.54) $$
# Chapitre 4

## Commande en juste-à-temps d'un GET

Nous nous sommes intéressés jusque là, à la caractérisation de la sortie d'un GET en fonction de son entrée. On peut également se pencher sur le problème inverse qui correspond en fait à trouver une entrée (chercher une commande) engendrant une sortie satisfaisant une consigne donnée. Le principe de la commande en juste-à-temps consiste dans le fait de trouver la plus grande entrée u du système telle que la sortie y ne dépasse pas une certaine consigne z donnée. C'est en fait un problème de poursuite de trajectoire en boucle ouverte. La commande en juste-à-temps va donc nous demander d'étudier un nouveau type d'inéquation/équation du style $f(x) \le b$, $f(x) = b$ dont on va chercher une solution optimale : cette étude fait appel à la théorie de la résiduation.

### 4.1 Quelques éléments de la théorie de la résiduation

#### 4.1.1 Fonctions résiduables et fonctions résiduées

La commande en juste-à-temps qui sera présentée dans la section suivante de ce chapitre nécessite au préalable l'étude des équations/inéquations de type :

$$f(x) = b \quad f(x) \le b \qquad (4.1)$$

où $f$ est une application d'un dioïde complet ($\mathcal{D}$, $\oplus$, $\otimes$) vers un dioïde complet ($C$, $\oplus$, $\otimes$), $b \in C$.<fnref n="1" /> La résolution de l'équation (4.1) nécessiterait d'inverser $f$ (en effet, $f(x) = b \Leftrightarrow x = f^{-1}(b)$ si un tel inverse $f^{-1}$ existait...). Or, les lois $\oplus$ et $\otimes$ constituant les dioïdes n'introduisent pas de notions d'inverse en général (un dioïde étant un semi-anneau idempotent, un dioïde n'est donc généralement pas un anneau où de tels inverses existeraient). Néanmoins, la théorie de la résiduation permet de définir des pseudo-inverses pour des applications définies sur des treillis, et donc plus particulièrement sur des dioïdes complets qui définissent des treillis complets. Plus précisément, la théorie de la résiduation permet d'établir, lorsqu'elle existe, la plus grande solution de l'inéquation $f(x) \le b$.

**Définition 13 (Application continue).** Une application $f$ est semi-continue inférieurement si pour tout sous-ensemble $X$ de $\mathcal{D}$ :

$$f(\bigoplus_{x \in X} x) = \bigoplus_{x \in X} f(x) \qquad (4.2)$$

Une application $f$ est semi-continue supérieurement si pour tout sous-ensemble $X$ de $\mathcal{D}$ :

$$f(\bigwedge_{x \in X} x) = \bigwedge_{x \in X} f(x) \qquad (4.3)$$

<footnote n="1">1. On utilisera les notations $\oplus$ et $\otimes$ de façon indifférenciée sur les dioïdes $\mathcal{D}$ et $C$ en fonction du contexte, mais l'opérateur $\oplus$ (resp. $\otimes$) sur $\mathcal{D}$ n'est pas le même que $\oplus$ (resp. $\otimes$) sur $C$.</footnote>
Une application *f* est continue si elle est à la fois, semi-continue inférieurement et semi-continue supérieurement.

Le théorème suivant est le résultat fondateur pour la recherche de solutions aux équations
du type $f(x) = b$ où $f$ doit être une fonction à minima isotone et semi-continue inférieurement.

**Théorème 6.** Soit $f$ une application isotone d'un dioïde complet $\mathcal{D}$ vers un dioïde complet $C$, les trois conditions suivantes sont équivalentes :

1. Pour tout $b \in C$, il existe une plus grande sous solution à l'équation $f(x) = b$ (c.-à-d. l'ensemble des solutions de $f(x) \le b$ n'est pas vide et admet une solution maximale unique);

2. Il existe une application $f^{\#}$, isotone et semi-continue supérieurement, de $C$ vers $\mathcal{D}$ telle que :

$$
\forall y \in C, f \circ f^{\#}(y) \leq y \qquad (4.4)
$$

$$
\forall x \in \mathcal{D}, f^{\#} \circ f(x) \geq x \qquad (4.5)
$$

3. L'application $f$ est semi-continue inférieurement et $f(\varepsilon) = \varepsilon$.

Démonstration.

**Implication** (1 $\Rightarrow$ 2)

1. Pour tout $b \in C$, l'ensemble des solutions de $f(x) \le b$ n'est pas vide et admet une solution maximale unique alors notons cette solution $f^{\#}(b)$. Donc $f^{\#}$ est une application de $C$ vers $\mathcal{D}$. Soit $a, b \in C$ tel que $a \le b$. Par définition de $f^{\#}$ on a $f^{\#}(a) = \bigoplus_{x|f(x) \le a} x$ or $a \le b$ donc $f^{\#}(a)$ est une solution de $f(x) \le b$. Sachant que $f^{\#}(b)$ est la plus grande solution de $f(x) \le b$, on $f^{\#}(a) \le f^{\#}(b) : f^{\#}$ est une application isotone, elle préserve l'ordre.

2. Soit $y \in C$, par définition de $f^{\#}$, $f^{\#}(y)$ est une solution de $f(x) \le y$ donc $f(f^{\#}(y)) \le y$ (équation (4.4));

3. Soit $x \in \mathcal{D}$. Notons $b = f(x)$, donc $f(x) \le b$. Or la plus grande solution de $f(x) \le b$ est $f^{\#}(b)$, ce qui implique que $x \le f^{\#}(b) = f^{\#}(f(x))$ (équation (4.5)).

4. Démontrons enfin que $f^{\#}$ est semi-continue supérieurement. Soit $B$ un sous-ensemble quelconque de $C$. L'élément $\bigwedge_{b \in B} b$ est la borne inférieure de $B$ dans le dioïde complet $C$. Comme $f^{\#}$ est isotone $\forall x \in B$, $f^{\#}(\bigwedge_{b \in B} b) \le f^{\#}(x)$, autrement dit $f^{\#}(\bigwedge_{b \in B} b)$ est inférieur à la borne inférieure de $\{f^{\#}(x), x \in B\}$, donc

$$
f^{\#}\left(\bigwedge_{b \in B} b\right) \leq \bigwedge_{b \in B} f^{\#}(b) \qquad (4.6)
$$

De même *f* est également une fonction isotone : l'image par *f* de la borne inférieure de
{f<sup>#</sup>(b), b ∈ B} est nécessairement inférieure à la borne inférieure des images de chaque
f<sup>#</sup>(b), b ∈ B, formellement :

$$
f\left(\bigwedge_{b \in B} f^{\#}(b)\right) \leq \bigwedge_{b \in B} f\left(f^{\#}(b)\right) \qquad (4.7)
$$

Or l'équation (4.4) nous indique que pour tout $b \in B$, on a $f(f^{\#}(b)) \le b$ et donc les bornes inférieures sont telles que :

$$
\bigwedge_{b \in B} f(f^{\#}(b)) \le \bigwedge_{b \in B} b \qquad (4.8)
$$

et donc par transitivité de l'ordre $\le$ :
$$f\left(\bigwedge_{b \in B} f^{\#}(b)\right) \leq \bigwedge_{b \in B} b \qquad (4.9)$$

Ainsi, $\bigwedge_{b \in B} f^{\#}(b)$ est solution de $f(x) \leq \bigwedge_{b \in B} b$ mais comme la plus grande d'entre elles est $f^{\#}(\bigwedge_{b \in B} b)$ on a :

$$\bigwedge_{b \in B} f^{\#}(b) \leq f^{\#}\left(\bigwedge_{b \in B} b\right) \qquad (4.10)$$

Les équations (4.6) et (4.10) imposent alors l'égalité :

$$\bigwedge_{b \in B} f^{\#}(b) = f^{\#}\left(\bigwedge_{b \in B} b\right) \qquad (4.11)$$

Donc $f^{\#}$ est bien semi-supérieurement continue.

**Implication (2 ⇒ 3)**

1. L'équation (4.4) impose que $f(f^{\#}(\varepsilon)) \leq \varepsilon$ mais $\varepsilon$ est le plus petit élément de $C$ et donc $f(f^{\#}(\varepsilon)) = \varepsilon$. Mais on a également $f^{\#}(\varepsilon) \geq \varepsilon$ (pour la même raison que $\varepsilon$ est le plus petit élément de $C$). L'isotonie de $f$ impose alors que $f(f^{\#}(\varepsilon)) \geq f(\varepsilon)$ et donc au final $f(\varepsilon) = \varepsilon$.

2. Soit $X \subseteq D$. L'isotonie de $f$ implique que la borne supérieure des images de $x \in X$ par $f$ est inférieure à l'image de la borne supérieure de $X$, formellement :

$$\bigoplus_{x \in X} f(x) \leq f\left(\bigoplus_{x \in X} x\right) \qquad (4.12)$$

Soit $x \in X$, on note $b_x = f(x)$. L'équation (4.5) impose que $f^{\#}(b_x) \geq x$. Par l'isotonie de $f$, on a ainsi :

$$f\left(\bigoplus_{x \in X} x\right) \leq f\left(\bigoplus_{x \in X} f^{\#}(b_x)\right) \qquad (4.13)$$

Par l'isotonie de $f^{\#}$, on a également :

$$\bigoplus_{x \in X} f^{\#}(b_x) \leq f^{\#}\left(\bigoplus_{x \in X} b_x\right) \qquad (4.14)$$

Par l'isotonie de $f$, on obtient alors que :

$$f\left(\bigoplus_{x \in X} x\right) \leq f\left(f^{\#}\left(\bigoplus_{x \in X} b_x\right)\right) \qquad (4.15)$$

Et l'équation (4.4) impose alors :

$$f\left(\bigoplus_{x \in X} x\right) \leq \bigoplus_{x \in X} b_x = \bigoplus_{x \in X} f(x) \qquad (4.16)$$

Les équations (4.16) et (4.12) imposent alors l'égalité :

$$\bigoplus_{x \in X} f(x) = f\left(\bigoplus_{x \in X} x\right) \qquad (4.17)$$

Donc $f$ est bien semi-inférieurement continue.
**Implication (3 ⇒ 1)**

On sait que $f(\varepsilon) = \varepsilon$ donc pour tout $b \in C$, $f(x) \leq b$ a nécessairement $\varepsilon$ comme solution donc l'ensemble $X_b$ des solutions de $f(x) \leq b$ n'est pas vide. $f$ est semi-inférieurement continue donc pour tout $b \in C$

$$ \bigoplus_{x \in X_b} f(x) = f\left(\bigoplus_{x \in X_b} x\right) \qquad (4.18) $$

$X_b$ est l'ensemble des solutions de $f(x) \leq b$ donc $\bigoplus_{x \in X_b} f(x) \leq b$ et donc

$$ f\left(\bigoplus_{x \in X_b} x\right) \leq b \qquad (4.19) $$

autrement dit $(\bigoplus_{x \in X_b} x)$ est solution de $f(x) \leq b$ de plus, par définition cette solution est maximale et donc unique. □

Le théorème 6 affirme ainsi qu'il existe des fonctions $f$ pour lesquelles il existe toujours une plus grande sous solution à l'équation $f(x) = b$. Ces fonctions sont dites résiduables.

**Définition 14 (Fonction résiduable).** Une fonction $f : \mathcal{D} \to C$ est résiduable si elle satisfait les conditions du théorème 6, à savoir :

1. $f$ est isotone;

2. $f$ est semi-continue inférieurement;

3. $f(\varepsilon) = \varepsilon$.

Ainsi, le théorème 6 indique que si $f$ est résiduable, on peut définir une fonction $f^\# : C \to \mathcal{D}$ telle que $\forall b \in C$, $f^\#(b)$ est la plus grande solution de $f(x) \leq b$ (voir la preuve du théorème 6). On n'a pas la garantie que $f(f^\#(b)) = b$ mais l'on sait que si $f(f^\#(b)) \neq b$ il n'existe pas de $x \geq f^\#(b)$ tel que $f(x) \leq b$. Autrement dit $f^\#$ joue le rôle d'une pseudo-inverse de $f$ :

$$ f(x) = b \approx x = f^\#(b). $$

La fonction $f^\#$ ainsi définie dans la preuve du théorème 6 est la résiduée de $f$ et le théorème 6 garantit qu'elle existe pour toute fonction résiduable $f$.

**Définition 15 (Fonction résiduée).** Soit une fonction $f : \mathcal{D} \to C$ résiduable, la résiduée de $f$ est la fonction $f^\# :$

$$ f^\# : \begin{array}{ccc} C & \to & \mathcal{D} \\ b & \mapsto & \bigoplus_{\{x|f(x) \leq b\}} x \end{array} \qquad (4.20) $$

### 4.1.2 Résiduée de la fonction $L_a(x) = ax$

Nous allons maintenant étudier une fonction résiduable particulière, c'est la fonction :

$$ L_a : \begin{array}{ccc} \mathcal{D} & \to & C \\ x & \mapsto & ax \end{array} \qquad (4.21) $$

C'est cette fonction qui sera exploitée pour la commande en juste-à-temps dans la section suivante. Tout d'abord, cette fonction est-elle résiduable ? La réponse est affirmative, pour s'en convaincre, vérifions si $L_a$ a toutes les propriétés requises.

1. Elle est isotone (car le produit est isotone);
2. Elle est semi-continue inférieurement. En effet, soit $X$ un sous-ensemble de $\mathcal{D}$, on a

$$a \bigoplus_{x \in X} x = \bigoplus_{x \in X} ax$$

car $\mathcal{D}$ et $\mathcal{C}$ sont des dioïdes complets.

3. Enfin on a $L_a(\varepsilon) = a\varepsilon = \varepsilon$ par définition d'un dioïde ($\varepsilon$ est absorbant pour $\otimes$).

La fonction résiduée de $L_a$ est donc :

$$L_a^\# : \left| \begin{array}{c} C \rightarrow \\ b \mapsto \end{array} \right. \mathcal{D} \oplus_{\{x|ax \le b\}} x \qquad (4.22)$$

Cette fonction est notée également :

$$L_a^\#(b) = a\varepsilon b = \frac{b}{a} = \bigoplus_{\{x|ax \le b\}} x$$

**Quelques propriétés de $a\varepsilon b$ :**

— Par définition, $a\varepsilon b$ est la plus grande solution de $ax \le b$, donc :

$$ax \le b \Leftrightarrow x \le a\varepsilon b. \qquad (4.23)$$

— Deux autres résultats intéressants :

$$a\varepsilon(x \wedge y) = a\varepsilon x \wedge a\varepsilon y \qquad (4.24)$$

$$a\varepsilon(x \oplus y) \ge a\varepsilon x \oplus a\varepsilon y \qquad (4.25)$$

Démontrons 4.24 :

$$a\varepsilon x \wedge a\varepsilon y = \bigoplus_{z|z \le a\varepsilon x, z \le a\varepsilon y} z = \bigoplus_{z|a\varepsilon x, z \le y} z = \bigoplus_{z|a\varepsilon x \wedge y} z = a\varepsilon(x \wedge y) \qquad (4.26)$$

Démontrons 4.25 :

$$a\varepsilon(x \oplus y) = \left( \bigoplus_{z|az \le x \oplus y} z \right) = \left( \bigoplus_{z|az \le x \oplus y} z \right) \oplus \left( \bigoplus_{z|az \le x} z \right) \oplus \left( \bigoplus_{z|az \le y} z \right) = a\varepsilon x \oplus y \oplus a\varepsilon x \oplus a\varepsilon y \qquad (4.27)$$

et donc :

$$a\varepsilon(x \oplus y) \ge \oplus a\varepsilon x \oplus a\varepsilon y \qquad (4.28)$$

L'ensemble des égalités usuelles des résiduées de type $a\varepsilon b$ est en annexe A.

## Exemple 1.

*Sur $\mathbb{Z}_{max}$, que vaut $3\varepsilon 8$ ?*

Par définition $3\varepsilon 8 = \bigoplus_{x|3x \le 8} x$, c'est la plus grande solution de $3 \otimes x \le 8$ sur $\mathbb{Z}_{max}$. Autrement dit, en remplaçant $\otimes$ par $+$ et rappelant que l'ordre de $\mathbb{Z}_{max}$ est l'ordre naturel, on cherche la plus grande solution de $3 + x \le 8$ donc $3\varepsilon 8 = 5$.

*Sur $\mathbb{Z}_{max}$, que vaut $8\varepsilon 3$ ?*
C'est la plus grande solution de $8 + x \le 3$ sur $\mathbb{Z}_{\text{max}}$ donc $3 \nparallel 8 = -5$.

Et $3 \nparallel 8$ sur $\mathbb{Z}_{\text{min}}$ ?

C'est toujours la plus grande solution de $3 \otimes x \le 8$ mais sur $\mathbb{Z}_{\text{min}}$. Autrement dit, en remplaçant $\otimes$ par $+$ et rappelant que l'ordre de $\mathbb{Z}_{\text{min}}$ est l'ordre inverse, on cherche la plus petite solution de $3 + x \ge 8$ donc $3 \nparallel 8 = 5$.

Et $8 \nparallel 3$ sur $\mathbb{Z}_{\text{min}}$ ?

C'est toujours la plus grande solution de $8 \otimes x \le 3$ mais sur $\mathbb{Z}_{\text{min}}$. Autrement dit, en remplaçant $\otimes$ par $+$ et rappelant que l'ordre de $\mathbb{Z}_{\text{min}}$ est l'ordre inverse, on cherche la plus petite solution de $8 + x \ge 3$ donc $3 \nparallel 8 = -5$.

### 4.1.3 Cas matriciel $L_A(X) = AX$

On considère maintenant la version matricielle de $L_a$ définies sur les ensembles de matrices à coefficients dans le dioïde complet ($\mathcal{D}, \oplus, \otimes$). Soit $A \in \mathcal{D}^{n \times p}$ une matrice sur $\mathcal{D}$. On définit $L_A$ :

$$ L_A : \left| \begin{array}{ccc} \mathcal{D}^{p \times q} & \rightarrow & \mathcal{D}^{n \times q} \\ X & \mapsto & AX \end{array} \right. \qquad (4.29) $$

On peut démontrer en s'appuyant sur $L_a$ que l'application $L_A$ est également résiduable. De plus, le théorème 6 s'étend au cas matriciel et donc une équation matricielle du type $AX = B$, où $B$ est une matrice $\mathcal{D}^{n \times q}$, admet comme plus grande sous-solution la résiduée de $L_A$ sur $B$ :

$$ L_A^{\sharp} : \left| \begin{array}{ccc} \mathcal{D}^{n \times q} & \rightarrow & \mathcal{D}^{p \times q} \\ B & \mapsto & \bigoplus_{\{X,AX \le B\}} X \end{array} \right. \qquad (4.30) $$

Cette résiduée $L_A^{\sharp}(B)$ est également notée $A \nparallel B$.

**Comment calculer $A \nparallel B$ ?**

On note :

$$ A = \begin{pmatrix} a_{11} & \cdots & a_{1p} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{np} \end{pmatrix} \quad B = \begin{pmatrix} b_{11} & \cdots & b_{1q} \\ \vdots & & \vdots \\ b_{n1} & \cdots & a_{nq} \end{pmatrix} \quad A \nparallel B = \begin{pmatrix} c_{11} & \cdots & c_{1q} \\ \vdots & & \vdots \\ c_{p1} & \cdots & c_{pq} \end{pmatrix} \qquad (4.31) $$

Une composante de $A \nparallel B$ est donnée par :

$$ c_{ij} = \bigwedge_{k=1}^{n} a_{ki} \nparallel b_{kj} \quad \forall i \in \{1, \dots, p\}, j \in \{1, \dots, q\} \qquad (4.32) $$

**Exemple 2.** Soient $A = \begin{pmatrix} 2 & 5 \\ \varepsilon & 3 \\ 1 & 8 \end{pmatrix}$ et $B = \begin{pmatrix} 6 \\ 4 \\ 9 \end{pmatrix}$ deux matrices sur $\mathbb{Z}_{\text{max}}$. On a :

$$ A \nparallel B = \begin{pmatrix} 4 \\ 1 \end{pmatrix} $$

En effet :

$$ c_{11} = a_{11} \nparallel b_{11} \wedge a_{21} \nparallel b_{21} \wedge a_{31} \nparallel b_{31} \qquad (4.33) $$

$$ = 2 \nparallel 6 \wedge \varepsilon \nparallel 4 \wedge 1 \nparallel 9 \qquad (4.34) $$

$$ = 4 \wedge +\infty \wedge 8 = 4 \qquad (4.35) $$
$$c_{21} = a_{12} \oplus b_{11} \wedge a_{22} \oplus b_{21} \wedge a_{32} \oplus b_{31} \qquad (4.36)$$

$$= 5 \oplus 6 \wedge 3 \oplus 4 \wedge 8 \oplus 9 \qquad (4.37)$$

$$= 1 \wedge 1 \wedge 1 = 1 \qquad (4.38)$$

## 4.2 Application à la commande en juste-à-temps

Dans cette section, on considère un GET non-autonome régi par le système de représentation dateur dans $Z_{max}$ de la forme :

$$x(k) = Ax(k-1) \oplus Bu(k)$$

$$y(k) = Cx(k)$$

On note $n$ le nombre de sorties du système. $y$ est ainsi un vecteur de $n$ fonctions dateurs $y_i$.

### 4.2.1 Caractérisation de la commande en juste-à-temps

On définit la consigne $z$ comme un vecteur de $n$ fonctions dateurs.

**Définition 16 (Consigne z).** La consigne $z$ du système est un vecteur

$$z = \begin{bmatrix} z_1 \\ \vdots \\ z_n \end{bmatrix}$$

où $z_i$ est une fonction dateur servant de consigne pour la sortie $y_i$. Le système de sortie $y$ respecte la consigne $z$ si :

$$y \leq_d z$$

autrement dit,

$$\forall i \in \{1, \dots, n\}, \forall k \in Z, y(k) \leq z(k)$$

L'un des objectifs de la commande est donc de déterminer une entrée $u$ (vecteur de fonctions dateurs) telle que l'ensemble des événements produits sur la sortie $y$ sont toujours produits avant une certaine date limite (la production du $k^{ème}$ événement sur la sortie $y_i$ doit avoir lieu avant la date $z_i(k)$). La commande en juste-à-temps doit non seulement répondre en premier lieu à cet objectif mais aussi cette commande doit être optimale dans le sens où elle doit être la plus tardive possible. On rappelle ici qu'à partir d'une représentation d'états, on peut établir une relation d'entrée sortie entre les dateurs $u$ et les dateurs $y$ (voir la section 3.3.2) :

$$y = H u = C A^* B u.$$

Le problème de la commande en juste à temps est donc de déterminer le dateur $u_{opt}$ qui est la plus grande solution à l'inéquation suivante :

$$H u \leq_d z \qquad (4.39)$$

Cette inéquation est de la forme présentée en section 4.1.3, la matrice $H$ ne dépendant pas de $u$ et de $z$. La théorie de la résiduation, à travers le théorème 6 et son extension au cas matriciel, montre donc que la commande en juste à temps $u_{opt}$ existe toujours, de plus elle est caractérisée par la résiduée de la fonction $L_H$.
**Théorème 7.** La commande en juste à temps $\mathbf{u}_{opt}$ existe toujours, et est caractérisée par :

$$ \mathbf{u}_{opt} = H \mathbf{z} = \bigoplus_{\mathbf{u} \in \mathcal{D}_d | H \mathbf{u} \leq_d \mathbf{z}} \mathbf{u}. \qquad (4.40) $$

*Démonstration.* Le résultat est immédiat, issu de la théorie de la résiduation et en particulier du théorème 6. □

### 4.2.2 Synthèse effective de la commande en juste à temps

Dans cette section, nous allons montrer comment on peut effectivement synthétiser à l'aide d'un algorithme de calcul récursif sur $\mathbb{Z}_{max}$ la commande en juste à temps répondant à une consigne $\mathbf{z}$. Cet algorithme est basé sur le résultat suivant.

**Théorème 8.** La commande en juste à temps $\mathbf{u}_{opt}$ est la plus grande solution de

$$ \xi = A \mathbf{z} \wedge C \mathbf{z} \qquad (4.41) $$

$$ \mathbf{u} = B \mathbf{z} \qquad (4.42) $$

*Démonstration.*

1. Démontrons dans un premier temps que $\mathbf{u}_{opt}$ est bien solution de (4.43). On pose

$$ \xi = CA^* \mathbf{z} $$

L'équation (4.40) associée à l'égalité (A.9) nous donne :

$$ \mathbf{u}_{opt} = H \mathbf{z} = (CA^*B) \mathbf{z} = B \mathbf{z}(CA^* \mathbf{z}) $$

Donc la seconde égalité de (4.43) est vérifiée. Il ne reste qu'à démontrer que $(CA^*) \mathbf{z} = A \mathbf{z}((CA^*) \mathbf{z}) \wedge C \mathbf{z}$

$$ A \mathbf{z}((CA^*) \mathbf{z}) \wedge C \mathbf{z} = (ACA^*) \mathbf{z} \wedge C \mathbf{z} \qquad (\text{par l'égalité (A.9)}) $$

$$ = (CA^+) \mathbf{z} \wedge C \mathbf{z} \qquad (\text{par l'égalité } A^+ = AA^*) $$

$$ = (CA^+ \oplus C) \mathbf{z} \qquad (\text{par l'égalité (A.3)}) $$

$$ = (CA^*) \mathbf{z} \qquad (\text{par définition de l'opérateur } *) $$

2. Démontrons maintenant que toute solution $\mathbf{u}$ de (4.43) est bien majorée par $\mathbf{u}_{opt}$. Soit $\xi$ une solution à la première équation de (4.43) :

$$ \begin{align*} \xi &= A \mathbf{z} \wedge C \mathbf{z} = A \mathbf{z} (A \mathbf{z} \wedge C \mathbf{z}) \wedge C \mathbf{z} \\ &= (A \mathbf{z} (A \mathbf{z}) \wedge A \mathbf{z} (C \mathbf{z})) \wedge C \mathbf{z} \qquad (\text{par l'égalité (A.1)}) \end{align*} $$

$$ = A^2 \mathbf{z} \wedge (CA) \mathbf{z} \wedge C \mathbf{z} \qquad (\text{par l'égalité (A.9)}) $$

$$ = A^2 \mathbf{z} (A \mathbf{z} \wedge C \mathbf{z}) \wedge (CA) \mathbf{z} \wedge C \mathbf{z} $$

$$ \therefore = A^n \mathbf{z} \wedge \bigwedge_{i=0}^{n-1} (CA^i) \mathbf{z} \qquad \text{pour tout } n \ge 0 $$

$$ \le \bigwedge_{i=0}^{n-1} (CA^i) \mathbf{z} \qquad \text{pour tout } n \ge 0 $$

$$ \le (CA^*) \mathbf{z} $$
La deuxième équation de (4.43) nous donne $\mathbf{u}$ en fonction de $\xi$ :

$$ \mathbf{u} = B \xi $$

or

$$ \xi \le (CA^*) \mathbf{z} $$

donc par définition de la résiduée :

$$ \mathbf{u} \le (CA^*B) \mathbf{z} = \mathbf{u}_{\text{opt}}. $$

Toute solution $\mathbf{u}$ de (4.43) est bien majorée par $\mathbf{u}_{\text{opt}}$. $\square$

## Algorithme de calcul effectif de la commande en juste à temps sur $\mathbb{Z}_{max}$ (ou $\mathbb{R}_{max}$)

En pratique, la consigne $\mathbf{z}$ est une consigne qui fixe la date d'un nombre fini $K$ d'événements. Ainsi, pour toute composante $z_i$ de $\mathbf{z}$, on a :

1. $z_i(k) = \epsilon$ pour tout $k < 0$ (les événements numérotés négativement ont lieu à la date $\epsilon = -\infty$);

2. $z_i(k) = \top$ pour tout $k \ge K$ (les événements numérotés après $K$ n'arrivent jamais, leur date est $\top = +\infty$).

La consigne $\mathbf{z}$ est donc caractérisée par une séquence de $K$ vecteurs de dates :

$$ \mathbf{z}(0) = \begin{bmatrix} z_1(0) \\ \vdots \\ z_n(0) \end{bmatrix} \mathbf{z}(1) = \begin{bmatrix} z_1(1) \\ \vdots \\ z_n(1) \end{bmatrix} \dots \mathbf{z}(K) = \begin{bmatrix} z_1(K-1) \\ \vdots \\ z_n(K-1) \end{bmatrix} $$

et pour tout $k < 0$, $\mathbf{z}(k) = \epsilon$ et pour tout $k \ge K$, $\mathbf{z}(k) = \top$.

En s'appuyant sur les équations (4.43) sur les dateurs, on en déduit les equations suivantes sur les dates, pour tout $k \ge 0$ :

$$ \xi(k) = A \xi(k+1) \land C \mathbf{z}(k) \quad (4.43) $$

$$ \mathbf{u}(k) = B \xi(k) \quad (4.44) $$

Pour tout $k \ge K$, on a $\mathbf{z}(k) = \top$ cela induit que la commande $\mathbf{u}(k)$ est telle que $\mathbf{u}(k) = \top$ (le $k^{\text{ème}}$ événement ne se produit pas sur $\mathbf{u}$). Ainsi, on a également $\xi(k) = \top$. Ainsi, à partir de $k = K - 1$, on peut calculer par récursivité inverse $\mathbf{u}(K - 1), \dots, \mathbf{u}(0)$ en suivant l'algorithme suivant.

**Entrées** : matrices $A, B, C$ de la représentation d'état

**Entrées** : consigne $\mathbf{z}(0) \dots \mathbf{z}(K-1)$

$k \leftarrow K$

$\xi(k) \leftarrow \top$

**tant que** $k > 0$ faire

$$ \left| \begin{array}{l} k \leftarrow k-1 \\ \xi(k) \leftarrow A \xi(k+1) \land C \mathbf{z}(k) \\ \mathbf{u}(k) \leftarrow B \xi(k) \end{array} \right. $$

fin

**Sorties** : commande $\mathbf{u}(0) \dots \mathbf{u}(K-1)$
# Chapitre 5

## Systèmes autonomes (max, +)-linéaires

<figure><img src="image_11.png" /><figcaption>FIGURE 5.1 – Système autonome</figcaption></figure>

### 5.1 Simulation

Certains systèmes (max, +)-linéaires possèdent la particularité d’être autonomes, c’est-à-dire qu’ils ne comportent pas d’entrées<fnref n="1" />. Leur évolution est donc uniquement décrite à partir des conditions initiales et de la matrice d’évolution $A$, c’est le cas notamment du système représenté par la figure 5.1 (voir sa description dans la section 3.1.1) et dont les équations aux dateurs (dans $\mathbb{R}_{max}$) sont les suivantes :

$$x_1(k) = 1 \otimes x_1(k-1) \oplus 8 \otimes x_2(k-1) \qquad (5.1)$$

$$x_2(k) = 3 \otimes x_2(k-1) \oplus 2 \otimes x_1(k-1) \qquad (5.2)$$

Ce système est simple et sa mise en équation est déjà en représentation d’états<fnref n="2" /> qui prend alors la forme suivante :

$$x(k) = Ax(k-1)$$

Si on applique le même principe de récurrence que pour la définition de la réponse impul-
sionnelle, on obtient :

<footnote n="1">1. ou encore que l'influence des entrées sur l'évolution de l'état peut être négligée (typiquement, $u(k) = \epsilon, \forall k$).</footnote>

<footnote n="2">2. Dans cet exemple simple, on n'a pas de problème de retard nécessitant des extensions événementielles, ni de problème d'équations implicites nécessitant le calcul de $\vec{A_0A_1}$.</footnote>
$$
\begin{align*}
\mathbf{x}(k) &= A\mathbf{x}(k-1) \\
&= A^2\mathbf{x}(k-2) \\
&= \vdots \\
&= A^p\mathbf{x}(k-p), \forall p \ge 0
\end{align*}
$$

et donc pour $p = 0$, on obtient :

$$
\mathbf{x}(k) = A^k \mathbf{x}(0)
$$

Ainsi, on peut remarquer que l'évolution de l'état peut être caractérisée simplement à partir
des puissances de la matrice d'évolution.

**Exemple de simulation** Reprenons le système présenté sur la figure 5.1. Afin de le simuler, nous devons tout d'abord définir le dateur pour l'occurrence du premier événement x(0). Dans le cas de ce système on constate que les deux transitions sont sensibilisées dès la date 0 et la sémantique du franchissement au plus tôt impose que les deux transitions sont tirées une première fois à la date 0 :

$$
\mathbf{x}(0) = \begin{bmatrix} x_1(0) \\ x_2(0) \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}
$$

Les dates de la deuxième occurrence de tir de $x_1$ et de $x_2$ est obtenue par :

$$
\mathbf{x}(1) = A\mathbf{x}(0) = \begin{bmatrix} 1 & 8 \\ 2 & 3 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \end{bmatrix} = \begin{bmatrix} (1 \otimes 0) \oplus (8 \otimes 0) \\ (2 \otimes 0) \oplus (3 \otimes 0) \end{bmatrix} = \begin{bmatrix} \max(1, 8) \\ \max(2, 3) \end{bmatrix} = \begin{bmatrix} 8 \\ 3 \end{bmatrix}
$$

$x_1$ et $x_2$ étant tirées à la date 0, le deuxième tir de $x_1$ se fera à la date de sa sensibilisation qui est dépendante de la place avec la durée la plus longue, donc à la date 8. Le deuxième tir de $x_2$ est quant à lui conditionné par l'attente de 3 sur une de ses places en amont.

$$
\mathbf{x}(2) = A^2 \mathbf{x}(0) = \begin{bmatrix} 10 & 11 \\ 5 & 10 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 11 \\ 10 \end{bmatrix}
$$

Le troisième tir de $x_1$ est à la date 11 et celui de $x_2$ est à la date 10.

5.2 Temps de cycle

Dans cette section, on s'intéresse au temps de cycle d'un système autonome. Pour des raisons de temps, nous limitons l'étude à une sous classe de systèmes autonomes : les GETs à graphes de précédence fortement connexes (voir la section 5.2.2).

5.2.1 Existence d'un temps de cycle dans les systèmes autonomes

On rappelle la représentation d'état d'un système autonome (dans $\mathbb{R}_{max}$).

$$
\mathbf{x}(k) = A\mathbf{x}(k-1)
$$

On admettra sans démonstration les résultats suivants (les démonstrations sont dans[BCOQ92]).
La classe de systèmes autonomes étudiées évolue sous deux régimes :
1. un régime transitoire : il s'agit du régime au démarrage du système qui est constitué de l'occurrence de K événements par transition ($K \ge 0$) et n'est constitué d'aucun composition périodique;

2. un régime périodique : c'est un régime de c événements par transition tel que, pour tout $k \ge K$, on a :

$$x(k + c) = \tau \otimes x(k) \qquad (5.3)$$

La valeur $\tau \in \mathbb{R}_{max}$ est le temps de cycle. Comme nous sommes dans $\mathbb{R}_{max}$, cela revient à écrire $x(k + c) = x(k) + \tau$, toutes les dates sont exactement décalées de $\tau$ après un cycle de tirs de c événements par transition. La valeur c est la cyclicité du système. C'est le nombre d'événements nécessaires pour effectuer un cycle entier dans le système. On définit également le temps de cycle moyen $\lambda$ tel que :

$$\tau = \lambda^c$$
$$x(k + c) = \lambda^c \otimes x(k)$$

Dans $\mathbb{R}_{max}$, cela se traduit par $\tau = c\lambda$, c'est le temps moyen entre deux occurrences d'événements dans le cycle.

**À propos du régime transitoire K** En ce qui concerne la longueur du transitoire déterminée par K, il n'est pas possible de donner une estimation en générale. Même pour un très petit système, le transitoire peut être arbitrairement long. Des techniques de calcul de type programmation linéaire en nombre entier (PLNE) peuvent être employées.

### 5.2.2 Calcul du temps de cycle moyen $\lambda$

**Graphe de précédence :** La matrice A du système autonome est de la forme :

$$x(k) = Ax(k-1) = \begin{bmatrix} A(1,1) & \dots & A(1,n) \\ \vdots & \ddots & \vdots \\ A(n,1) & \dots & A(n,n) \end{bmatrix} x(k-1)$$

et on a $x_i(k) = \bigoplus_{j=1}^n A(i, j)x_j(k-1)$. Graphiquement sur un GET, si $A(i, j) \neq \varepsilon$, la relation entre la transition $x_i$ et la transition $x_j$ est caractérisée par un chemin constitué de la transition $x_j$ suivi d'une place associée au délai $A(i, j)$ et de la transition $x_i$. Ainsi, à travers la matrice A et sa composante $A(i, j)$, on peut caractériser un arc de précédence $x_j \xrightarrow{A(i,j)} x_i$ auquel on peut associer un poids $A(i, j)$ correspondant à une durée. Pour une telle matrice A, on peut ainsi définir un graphe de précédence $G(A)$ qui rassemble tous les arcs de précédence issus de A. Un chemin dans $G(A)$ est une séquence d'arcs $x_1 \xrightarrow{a_1} x_2 \xrightarrow{a_2} x_3 \dots$ et on dit que $G(A)$ est fortement connexe si pour tout couple $x_i, x_j$ il existe au moins un chemin entre $x_i$ et $x_j$.

**Exemple 3.** Le graphe de précédence du GET de la figure 5.1 est constitué de deux nœuds ($x_1$ et $x_2$) et de 4 arcs :

$$x_1 \xrightarrow{1} x_1, x_1 \xrightarrow{2} x_2, x_2 \xrightarrow{3} x_2, x_2 \xrightarrow{8} x_1$$

Ce graphe est fortement connexe.

**Chemins de transitions de durée maximale dans $G(A)$ :** Regardons maintenant la matrice

$$A^2 = \begin{bmatrix} A^2(1,1) & \dots & A^2(1,n) \\ \vdots & \ddots & \vdots \\ A^2(n,1) & \dots & A^2(n,n) \end{bmatrix}$$

Sa composante $A^2(i, j)$ est définie par :
$$A^2(i, j) = \bigoplus_{k=1}^{n} A(i, k)A(k, j)$$

et on a $x_i(k) = \bigoplus_{j=1}^{n} A^2(i, j)x_j(k-2)$. La composante $A^2(i, j)$ caractérise un arc de précédence sur $\mathcal{G}(A^2)$, il s'agit de l'arc $x_j \xrightarrow{A^2(i,j)} x_i$. Mais on peut également caractériser $A^2(i, j)$ sur le graphe de précédence de $A$, il s'agit du chemin de précédence de longueur 2 :

$$x_j \xrightarrow{A(i,l)} x_l \xrightarrow{A(l,i)} x_i \quad \text{tel que} \quad A^2(i,j) = A(i,l)A(l,j) = \bigoplus_{k=1}^{n} A(i,k)A(k,j)$$

Autrement dit $A^2(i, j)$ caractérise la durée maximale d'un chemin de longueur 2 entre $x_j$ et $x_i$: tous les chemins de longueur 2 entre $x_j$ et $x_i$ ont une durée inférieure ou égale à $A^2(i, j)$ et pour l'un d'entre eux au moins c'est égale à $A^2(i, j)$.

**Théorème 9.** Soit $A$ la matrice carrée associée à la représentation d'état d'un GET autonome, pour tout $n \ge 1$, la composante $A^n(i, j)$ de $A^n$ est telle que :

- si $A^n(i, j) \neq \varepsilon$, il existe au moins un chemin de précédence dans $\mathcal{G}(A)$ entre $x_j$ et $x_i$ de longueur $n$ et la durée maximale entre ces chemins est $A^n(i, j)$;

- si $A^n(i, j) = \varepsilon$, il n'existe pas de chemin de précédence dans $\mathcal{G}(A)$ entre $x_j$ et $x_i$ de longueur $n$.

**Cycle de durée maximale et temps moyen $\lambda$ :** Un circuit dans le graphe de précédence $\mathcal{G}(A)$ est un chemin de la transition $x_i$ vers elle-même. Ainsi la composante $A^n(i, i)$ de $A^n$ donne la durée maximale de tous les circuits de longueur $n$ qui mène de $x_i$ à $x_i$.

$$d_{max,n} = \bigoplus_{i=1}^{n} A^n(i, i) \qquad (5.4)$$

En cherchant à calculer $\lambda$, on cherche à déterminer un cycle (un circuit élémentaire, c.-à-d. un circuit issu d'une transition $x_i$ et dans lequel aucune autre transition $x_j$ n'apparaît plus d'une fois) tel que le rapport entre sa durée et sa longueur est maximale ($\lambda$ est appelé le temps de cycle moyen, il s'agit du temps moyen entre deux événements du cycle). Par construction, un cycle ne peut être de longueur supérieur à $n$. En utilisant les notations algébriques, on obtient donc :<fnref n="3" />

$$\lambda = \bigoplus_{j=1}^{n} d_{max,j}^{1/j} = \bigoplus_{j=1}^{n} \left( \bigoplus_{i=1}^{n} A^j(i, i) \right)^{1/j} \qquad (5.5)$$

**Théorème 10.** Soit un GET dont le graphe est fortement connexe, il existe une et une seule valeur propre pour sa matrice $A$ et cette valeur propre est le temps moyen $\lambda$.

En pratique, l'algorithme issu de l'équation (5.5) pour le calcul de $\lambda$ est le suivant.

Cet algorithme est naïf, d'autres algorithmes (algorithmes de Karp, de Howard) sont plus efficaces.

**Exemple 4.** Reprenons l'exemple de la figure 5.1.

$$A = \begin{bmatrix} 1 & 8 \\ 2 & 3 \end{bmatrix}, A^2 = \begin{bmatrix} 10 & 11 \\ 5 & 10 \end{bmatrix}$$

- $d_{max,1} = A(1,1) \oplus A(2,2) = 3, \lambda_1 = \frac{3}{1} = 3$.

- $d_{max,2} = A^2(1,1) \oplus A^2(2,2) = 10, \lambda_2 = \frac{10}{2} = 5$.

- $\lambda = \lambda_1 \oplus \lambda_2 = 5$.

Le temps moyen de cycle est $\lambda = 5$.

<footnote n="3">3. La notation algébrique $a^{1/j}$ signifie $\frac{a}{j}$ dans $\mathbb{R}_{max}$.</footnote>
**Entrées** : matrice A d'un GET autonome de taille $n \times n$

$\lambda \leftarrow \varepsilon$

$j \leftarrow 1$

tant que $j \le n$ faire

$$ 
\left|
\begin{array}{l}
d_{max,j} \leftarrow \bigoplus_{i=1}^{n} A^j(i, i) \\
\lambda_j \leftarrow \frac{d_{max,j}}{j} \\
\lambda \leftarrow \lambda \oplus \lambda_j \\
j \leftarrow j + 1
\end{array}
\right.
$$

fin

**Sorties** : Temps moyen $\lambda$

### 5.2.3 Calcul de la cyclicité c

La cyclicité $c$ est le nombre d'événements du cycle dont le temps moyen est $\lambda$. Dans le contexte des GETs autonomes dont le graphe de précédence est fortement connexe, le calcul de $c$ consiste à déterminer l'ensemble des cycles dont le temps moyen est $\lambda$ et de considérer $c$ comme le plus grand diviseur de la longueur de ces cycles.

**Entrées** : matrice A d'un GET autonome de taille $n \times n$ et de temps moyen $\lambda$

$C \leftarrow \emptyset$

$j \leftarrow 1$

pour chaque $j$ de 1 à $n$ faire

$$ 
\left|
\begin{array}{l}
\text{si } \lambda = \frac{d_{max,j}}{j} \text{ alors} \\
\quad C \leftarrow C \cup \{j\} \\
\text{fin}
\end{array}
\right.
$$

fin

$c \leftarrow \text{pgcd}(C)$

**Sorties** : Cyclicité $c$

**Exemple 5.** Reprenons l'exemple de la figure 5.1. On constate que seuls les circuits de longueurs 2 sont associés à $\lambda$ donc $C = \{2\}$ et donc la cyclicité est $c = 2$. Ainsi dans cet exemple, le temps de cycle est finalement :

$$ \tau = \lambda^c = 5^2 = 5 \otimes 5(\text{dans } \mathbb{R}_{max}) = 5 + 5(\text{dans } \mathbb{R}) = 10 $$
# Annexe A

## Égalités de résiduées $a \% b$

Cet annexe présente les (in)égalités usuelles impliquant des résiduées à gauche : $a \% b$. Tous les détails sont dans [BCOQ92]. Pour rappel :

$$a \% b = L_a(b) = \bigoplus_{x \in \mathcal{D} | ax \leq b} x$$

$$a \% (x \wedge y) = a \% x \wedge a \% y \qquad (A.1)$$

$$a \% (x \oplus y) \geq a \% x \oplus a \% y \qquad (A.2)$$

$$(a \oplus b) \% x = a \% x \wedge b \% x \qquad (A.3)$$

$$(a \wedge b) \% x \geq a \% x \oplus b \% x \qquad (A.4)$$

$$a(a \% x) \leq x \qquad (A.5)$$

$$a \% ax \geq x \qquad (A.6)$$

$$a(a \% ax) = ax \qquad (A.7)$$

$$a \% (a(a \% x)) = a \% x \qquad (A.8)$$

$$(ab) \% x = b \% (a \% x) \qquad (A.9)$$

$$b(a \% x) \leq (a \% b) \% x \qquad (A.10)$$

$$(a \% x)b \leq a \% xb \qquad (A.11)$$

$$(a \% x) \oplus b \leq x \% (x \oplus ab) \qquad (A.12)$$
# Annexe B

## Preuve du théorème du point fixe de Tarski

L'existence d'une plus petite solution à l'équation $x = ax \oplus b$ repose sur le théorème de point fixe dû à Alfred Tarski [Tar55]. Ce résultat fondamental pour l'algèbre (max, +) est principalement utilisé en informatique pour l'étude de la sémantique des langages de programmation, l'analyse de programme, la vérification automatique de modèle. Pour les curieux, nous reprenons ici le résultat et sa preuve détaillée qui repose sur la théorie des treillis.

**Théorème 11** (Théorème du point fixe dans un treillis). Soit $(E, \leq)$ un treillis complet, soit $f$ une fonction croissante de $E$ sur $E$, soit $P$ l'ensemble des points fixes de $f$ ($P = \{x|f(x) = x\}$), alors :

1. $P$ n'est pas vide;

2. $(P, \leq)$ forme un treillis complet;

3. le plus petit majorant de $P$ est le plus petit majorant de $\{x|x \leq f(x)\}$

4. le plus grand minorant de $P$ est le plus grand minorant de $\{x|f(x) \leq x\}$

Démonstration.

**Point 1** Soit $u$ le plus petit majorant de $\{x \in E | x \leq f(x)\}$ donc pour tout $x$ de cet ensemble $x \leq u$. Sachant que la fonction $f$ est croissante on a donc que $f(x) \leq f(u)$ et par transitivité $x \leq f(u)$. Ainsi $f(u)$ est un majorant de $\{x \in E | x \leq f(x)\}$ et comme $u$ est le plus petit de ces majorants, on obtient que $u \leq f(u)$. Comme $f$ est croissante $f(u) \leq f(f(u))$ ce qui implique que $f(u) \in \{x|x \leq f(x)\}$ et donc $f(u)$ est lui-même majoré par $u : f(u) \leq u$. Finalement $u \leq f(u) \leq u$ et l'antisymétrie de la relation d'ordre impose alors que $f(u) = u$. $u$ est donc un point fixe de $f$. Ainsi $P$ n'est pas vide.

**Point 3** Comme $u$ est un majorant de $\{x|x \leq f(x)\}$ c'est donc en particulier un majorant de $P$ et comme lui-même est un point fixe, il est donc le plus petit majorant de tous les points fixes.

**Point 4** Raisonnement identique au point 1. Soit $u$ le plus grand minorant de $\{x|f(x) \leq x\}$ donc pour tout $x$ de cet ensemble $u \leq x$. Sachant que la fonction $f$ est croissante on a donc que $f(u) \leq f(x)$ et par transitivité $f(u) \leq x$. $f(u)$ est donc un minorant de $\{x|f(x) \leq x\}$ et donc $f(u) \leq u$ puisque $u$ est le plus grand de ces minorants. Comme $f$ est croissante $f(f(u)) \leq f(u)$ ce qui implique que $f(u) \in \{x|f(x) \leq x\}$ et donc $f(u)$ est lui-même minoré par $u : u \leq f(u)$. Finalement $f(u) \leq u \leq f(u)$ donc $u$ est un point fixe. Comme $u$ est un minorant de $\{x|f(x) \leq x\}$ c'est donc en particulier un minorant de $P$ et comme lui-même est un point fixe, il est donc le plus petit minorant de tous les points fixes.

**Point 2** Considérons maintenant un sous-ensemble quelconque $Y$ de $P$, pour démontrer que $P$ est un treillis complet, il nous suffit de démontrer qu'il existe un plus petit majorant et
un plus petit minorant de $\mathcal{Y}$ dans $P$. Remarquons dans un premier temps que $\mathcal{Y}$ est un sous-ensemble du treillis complet $(E, \leq)$ et il a donc déjà un plus petit majorant dans $E$ que l'on note $\bar{x}_E$ et un plus grand minorant que l'on note $\underline{x}_E$.

1. Démontrons l'existence du plus petit majorant de $\mathcal{Y}$ dans $P$ (noté $\bar{x}_P$). Soit $\top$ la borne supérieure du treillis $(E, \leq)$, et $\bar{x}_E$ le plus petit majorant de $\mathcal{Y}$ dans $E$. On considère l'ensemble $U = \{x|\bar{x}_E \leq x \leq \top\}$. Par définition, cet ensemble constitue un treillis complet (sa borne inférieure est $\bar{x}_E$ et sa borne supérieure est $\top$ et contient tous les éléments de $(E, \leq)$ minoré par $\bar{x}_E$ et majoré par $\top$). Par construction, pour tout $x \in \mathcal{Y}$, $x \leq \bar{x}_E$. $f$ étant croissante, on obtient $f(x) \leq f(\bar{x}_E)$. Or $x$ étant dans $P$, c'est un point fixe ($x = f(x)$) et donc $x \leq f(\bar{x}_E)$. Ainsi $f(\bar{x}_E)$ majore tous les éléments de $\mathcal{Y}$ et comme $\bar{x}_E$ est le plus petit majorant de $\mathcal{Y}$, cela implique que $\bar{x}_E \leq f(\bar{x}_E)$, autrement dit $f(\bar{x}_E) \in U$. Pour tout $z \in U$ on a $\bar{x}_E \leq z$, et comme $f$ est croissante, cela implique que

$$ \bar{x}_E \leq f(\bar{x}_E) \leq f(z) $$

et $f(z) \in U$. Autrement dit, l'image de $f$ sur les éléments de $U$ est dans $U$. On peut donc définir la restriction $f'$ de $f$ sur $U$. $f$ étant croissante sur $E$, $f'$ est croissante sur $U$. Le résultat du point 4 s'applique alors sur $f'$ dans $U$ qui montre que $f'$ a un plus petit point fixe $v$ dans $U$ mais qui est également un point fixe $f$ dans $E$ donc $v \in P$. $v$ étant dans $U$, il majore tous les points fixes de $\mathcal{Y}$. $v$ étant également dans $P$, il existe donc un plus petit majorant $\bar{x}_P$ de $\mathcal{Y}$ dans $P$. Plus précisément, $\bar{x}_P = v$: en effet $U$ regroupe tous les majorants de $\mathcal{Y}$ qui sont dans $E$ et $v$ est le plus petit d'entre eux qui soit également dans $\mathcal{Y}$, aucun élément $x$ de $U$ tel que $\bar{x}_E \leq x \leq v$ et $x \neq v$ n'est dans $\mathcal{Y}$.

2. La démonstration de l'existence du plus grand majorant de $\mathcal{Y}$ dans $P$ (noté $\underline{x}_P$) est similaire à celle de l'existence de $\bar{x}_E$ en considérant $\underline{x}_E$ le plus grand minorant de $\mathcal{Y}$ dans $E$ et $U = \{x|\underline{x} \leq x \leq \underline{x}_E\}$.

L'existence pour tout $\mathcal{Y}$ de $\bar{x}_P$ et de $\underline{x}_P$ finalise la preuve du point 2. $\square$
Bibliographie

[BCOQ92] F. Baccelli, G. Cohen, G.J Olsder, and J.-P Quadrat. *Synchronization and linearity : an algebra for discrete event systems*. Wiley and sons, UK, 1992.

[BJ72] T.S. Blyth and M.F. Janowitz. *Residuation Theory*. Pergamon Press, 1972.

[Cor22] Euriell Le Corronc. Notes de cours, m2 istr 2022. Technical report, Université Toulouse III, 2022.

[Gau99] Stéphane Gaubert. Introduction aux systèmes dynamiques à événements discrets. Technical report, INRIA Rocquencourt, 1999.

[GM84] Michel Gondran and Michel Minoux. *Graphs and Algorithms*. Wiley, 1984.

[Har08] Laurent Hardouin. Sur la commande des systèmes (max,+)-linéaires. Technical report, Université d'Angers, 2008.

[Hou] Laurent Houssin. Commande des systèmes (max,+)-linéaires. Technical report.

[Tar55] Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. *Pacific journal of mathematics*, pages 285–309, 1955.