Convergence de la phase de propagation donnée par l'algorithme 2.1

Nous allons montrer que la phase de propagation se termine toujours: il n'y a pas de bouclage au cours de la modification des marquages $M_{i}$ et $M_{i,k}$. Pour cela, il faut noter que nous n'avons pas besoin de l'existence de la propriété ( $P_{\epsilon }$).
Soit S, la somme des marquages de l'ensemble des états perceptifs $e_{i}$ et des états transitoires $e_{i,k}$. Considérons à présent la valeur de S à l'instant t, notée S(t), et supposons qu'une nouvelle transition est découverte à cet instant. Admettons que cette transition relie l'état transitoire $e_{i,k}$ à l'état perceptif $e_{j}$. La valeur de $M_{i,k}$ dépend donc d'un nouveau marquage $M_{j}$.
Deux cas se présentent:

1. l'ajout de $M_{j}$ ne modifie pas le minimum des marquages des états connectés à $e_{i,k}$
2. la valeur de $M_{j}$ change le minimum des marquages des états connectés à $e_{i,k}$

Dans le premier cas, l'ajout de cette transition ne modifie pas la cohérence au niveau de $e_{i,k}$ et la phase de propagation n'est pas enclenchée.
Le second cas comporte deux sous-cas: soit la valeur minimum est augmentée par l'ajout du marquage $M_{j}$, soit elle est diminuée. Nous allons montrer que, dans les deux cas, la suite des modifications apportées aux marquages par la phase de propagation s'exprime par une évolution monotone de S.
Dans chacun des deux cas, $M_{i,k}$ doit être modifiée pour respecter la cohérence au niveau de l'état $e_{i,k}$. La valeur de $M_{i,k}$ est mise à $M_{j}$. Supposons que cette modification rende la nouvelle valeur de $M_{i,k}$ inférieure à la précédente: la nouvelle valeur S(t+1) est alors également inférieure à S(t) après cette modification. Examinons à présent la cohérence au niveau de l'état $e_{i}$. Deux cas de figure existent:

1. la modification de $M_{i,k}$ n'affecte pas le maximum des marquages des états $e_{i,k}$ connectés à l'état $e_{i}$
2. la valeur de $M_{i,k}$ change ce maximum

Dans le premier cas, la phase de propagation se termine, avec $S(t+1) < S(t)$.
Dans le second cas, la valeur de $M_{i}$ est incohérente. Or, le rétablissement de la cohérence, sachant que la nouvelle valeur de $M_{i,k}$ est inférieure à la précédente, se traduit par une diminution de la valeur de $M_{i}$, donc par une diminution de S: S(t+2) < S(t+1). Nous reprenons alors l'étape de modification au niveau de chaque état transitoire connecté à $e_{i}$. Et chacune de ces étapes conduit soit à une diminution de S, soit à un S inchangé (cas d'arrêt d'une branche de la phase de propagation). Par conséquent, la suite (S(t)) est décroissante. Comme la valeur de S est minorée par -n.(q+1) , on en déduit que la suite (S(t)) converge, ce qui signifie que la phase de propagation s'arrête.
Le même raisonnement peut être tenu lorsque la nouvelle valeur de $M_{i,k}$ est supérieure à la précédente. Dans ce cas, la suite (S(t)) est croissante. Or, elle est majorée par n.(q+1), donc elle converge.
Nous venons de montrer que la phase de propagation se termine toujours. Chaque état pour lequel la phase de propagation s'arrête est cohérent, par construction. Par conséquent, le fait de montrer que la propagation se termine est équivalent à dire que le graphe est cohérent après la phase de propagation.