Université Bordeaux I –
ENSEIRB - CNRS

Institut de la Francophonie  
pour  lʹInformatique

Laboratoire Bordelais de
Recherche en Informatique

Mémoire de fin d'études
"Dépliage du modèle en
langage AltaRica"

Préparé par NGUYEN Duy Tung
Sous la direction de M. COUVREUR Jean-Michel
et M. WALUKIEWICZ Igor

LaBRI, Octobre 2005


Dépliage du modèle en langage AltaRica

Page 1

Table des matières
1. Introduction générale ..........................................................................................................7
2. Langage AltaRica..................................................................................................................8
2.1
2.2
2.3

Introduction ................................................................................................................................8
Définition.....................................................................................................................................9
Transformation de l'AltaRica au réseau de Petri................................................................15

3. Dépliage de réseau de Petri.............................................................................................16
3.1
3.2
3.3

Notions élémentaires.............................................................................................................. 16
Etat de l'art ...............................................................................................................................18
Dépliage de produits d'automates ........................................................................................ 21

4. Réalisation............................................................................................................................26
4.1
4.2

Prototype ..................................................................................................................................26
Résultats...................................................................................................................................27

5. Amélioration.........................................................................................................................30
5.1
5.2
5.3

Dépliage basé sur le préfixe local......................................................................................... 30
Dépliage basé sur les techniques LCA et RMQ.................................................................34
Dépliage basé sur le RMQ dynamique ................................................................................40

6. Conclusion ...........................................................................................................................43

Référence....................................................................................................................................44
Annexe.........................................................................................................................................46
A. La syntaxe de langage AltaRica au format BNF........................................................................46
B. Tests standards en langage AltaRica..........................................................................................49
C. Algorithme de dépliage de produits d'automates ......................................................................51
D. Autres exemples de réseaux de Petri et leurs préfixes ............................................................58

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 2

Liste des figures
Figure 2.1
Figure 2.2
Figure 2.3
Figure 2.4
Figure 3.1
Figure 3.2a
Figure 3.2b
Figure 3.3
Figure 3.4
Figure 3.5a
Figure 3.5b
Figure 3.5c
Figure 3.6a
Figure 3.6b
Figure 3.6c

Figure 3.7
Figure 5.1
Figure 5.2
Figure 5.3
Figure 5.4
Figure 5.5
Figure 5.6
Figure 5.7
Figure 5.8

:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:

:
:
:
:

Réseau de Petri
Réseau de Petri de SG(3)
Macro-transition et des transitions correspondantes
SG(3) en langage AltaRica
Réseau d'ocurrence
Algorithme de dépliage
Génération des transitions
Préfixe fini
Préfixe du dépliage de SG(3)
Composant s0 de SG(3)
Composant s1 de SG(3)
Composant s2 de SG(3)
Processus arborescent dans le composant s0 de SG(3)
Processus arborescent dans le composant s1 de SG(3)
Processus arborescent dans le composant s2 de SG(3)
Processus arborescent global
Graphe des sous-préfixes
Les sous-préfixes Q, R et P de SG(3)
Graphe des sous-préfixes de SG(3)
L'arbre Cartsian du composant s1 de SG(3)
RMQ rapide
La construction du graphe des sous-préfixes
Construction de matrice A
Arbre AVL dans le RMQ dynamique


Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Liste des tableaux
Tableau 4.1
Tableau 4.2
Tableau 4.3
Tableau 4.4
Tableau 5.1

:
:
:
:
:

Résultats de dépliage du SG (avec une blanche)
Résultats de dépliage du SG (avec deux blanches)
Résultats de dépliage du DP
Résultats de dépliage du BUF
Comparaison de la complexité des algorithmes de dépliage

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX

Page 3


Dépliage du modèle en langage AltaRica


Page 4

Résumé
De nos jours, pour éviter l'explosion combinatoire du nombre d'états d'un système compliqué, la
vérification basée sur des préfixes finis est une bonne solution, mais le dépliage n'est développé
que sur le réseau de Petri, un langage de modélisation en bas niveau. Autrement dit, il ne
supporte pas un langage de modélisation en haut niveau comme l'AltaRica. Il faut construire un
outil de transformation pour résoudre ce problème.
D'autre part, grâce aux caractéristiques du modèle en AltaRica, on peut utiliser un dépliage plus
efficace, le dépliage de produits d'automates. De plus, dans leur dépliage local, nous pouvons
intégrer la technique basée sur le préfixe local ou les techniques Dernière Ancêtre Commun
(LCA) et Requête Minimale du Rang (RMQ) pour diminuer la complexité du problème.
Nous avons des implémentations expérimentales sur des tests standards pour tester la
correctivité et la performance des algorithmes de dépliage ainsi que des améliorations.

Mots clés: Dépliage, Altarica, réseau de Petri, modélisation, vérification, préfixe, Dernière
Ancêtre Commun (LCA), Requête Minimale du Rang (RMQ), RMQ dynamique

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 5

Abstract
Nowadays, for avoiding the combinational explosion of the states number of complex systems,
the model-checking based on finite prefix is a good solution but the unfolding is only developed
on the Petri net, a language of modelling in low-level. In other words, it does not support a

modelling language in high-level like AltaRica. We must build a tool of transformation in order to
resolve this problem.
On the other hand, because of features of model in AltaRica, we can use a more efficient
unfolding, this is a unfolding of products of automats. Furthermore, in their local unfolding, we
can integrate the technic based on the local prefixe or the technics Least Common Ancestor
(LCA), Range Minimum Query (RMQ) for reduce the complexity of the problem.
We have the experimental implementations on the standard tests in order to test the correctitude
and the performance of unfolding algorithms and their improvements.

Key-words: Unfolding, Altarica, Petri net, modelling, model-checking, prefix, Least Common
Ancestor (LCA), Range Minimum Query (RMQ), dynamic RMQ

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 6

Remerciement

Je tiens à remercier mes responsables, en particulier M. Jean-Michel COUVREUR qui m'a aidé à maîtriser le
sujet du stage, a corrigé mes fautes au début et m'a favorisé enfin de trouver de nouvelles solutions pour le
dépliage.
Je remercie M. André ARNOLD, M. Gérald POINT et M. Alaine GRIFFAULT qui me donnent des
documents intéressants concernant à l'AltaRica. Particulièrement M. André ARNOLD pour l'idée du LCA, et
M. Gérald POINT pour sa bibliothèque altatool pour que je puisse économiser le temps.
Je suis heureux d'avoir rencontré et de m'être intégré dans le groupe MVTsi (Modélisation, Vérification et Test
des systèmes informatisés), en particulier M. The Quang TRAN qui m'a aidé à surmonter des difficultés dans un
nouvel environnement.

Je remercie M. Victor KHOMENKO qui m'a donné des tests standards pour tester mes implémentations
expérimentales et les comparer avec les autres.
Je tiens à remercier les professeurs à l'IFI en particulier M. Thanh Thuy NGUYEN qui m'ont contribué des
meilleures conditions pour mon stage au LaBRI, Université Bordeaux 1.
Enfin, je veux envoyer un grand merci pour ma famille, mes amis qui ont partagé mes obstacles, m'ont favorisé
durant mon stage.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 7

1. Introduction générale
Né de la volonté d'industriels et de chercheurs, le langage de modélisation en haut niveau
AltaRica [Arnold03] a beaucoup d'avantages tels qu'il est utilisé plus facilement que des
langages de modélisation en bas niveau comme le réseau de Petri ou il est naturel de pouvoir
décrire par de nombreuses façons différentes un système donné.
La vérification basée sur des préfixes finis [Esparza01, Couvreur04] est une nouvelle approche
pour éviter l'explosion combinatoire de nombre d'états du système compliqué, mais ces
techniques ne sont développées que sur le réseau de Petri, un langage de modélisation en bas
niveau.
L'objectif de mon stage est de réaliser un dépliage sur le langage AltaRica: pas seulement de
construire un outil de tranformation de l'AltaRica au réseau de Petri, mais aussi de chercher des
algorithmes plus efficaces pour déplier un modèle en AltaRica.
Grâce aux caractéristiques du modèle en AltaRica, on peut utiliser un dépliage supplémentaire,
c'est le dépliage de produits d'automates [Esparza et al, 99, Couvreur04]. De plus, dans leur
dépliage local, pour améliorer la complexité du test de conflit, du test de la configuration ou la
complexité du problème en général, nous pouvons intégrer la technique basée sur le préfixe

local, les techniques Dernière Ancêtre Commun (LCA) ou Requête Minimale du Rang (RMQ)
[Demaine03, Bender00] et la technique basée sur le RMQ dynamique [Shibuya03].
L'introduction de langage AltaRica est donnée dans la section 2. Nous allons présenter l'état de
l'art du dépliage et le dépliage de produits d'automates dans la section 3.
En suite, on peut trouver aussi les implémentations expérimentales et les comparaisons entre le
dépliage normal et le dépliage de produits d'automates dans la section 4.
En fin, on discute sur les inconvénients et les améliorations du dépliage de produits d'automates
dans la section 5.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 8

2. Langage AltaRica
Langage AltaRica est un langage de modélisation en haut niveau ayant des avantages tels que
la construction des systèmes complexes plus facile que des langages de modélisation en bas
niveau comme le réseau de Petri. Plus en détail dans [Arnold03].

2.1 Introduction
Le projet AltaRica est né de la volonté d'industriels et de chercheurs pour établir divers ponts
entre :
•

la sûreté de fonctionnement et les méthodes formelles,

•


les analyses quantitatives des dysfonctionnements et les analyses qualitatives des
comportements fonctionnels,

•

les divers outils et méthodes d'aide à la modélisation,

afin de fournir aux ingénieurs concepteurs de systèmes complexes où critiques un atelier outillé.
Dans ce contexte, un outil de la vérification d'AltaRica basé sur le préfixe est attentatif.
Ce projet commence depuis 1996 et se compose de trois phases.
AltaRica : phase I (de Novembre 1996 à Octobre 1997)
Objectifs :
Etude de la faisabilité de couplages de différents outils en précisant si nécessaire la
sémantique de certains d'entre eux.
Résultats :
Définition d'un langage de description
l'expérimentation sur des cas tests.

de

systèmes

complexes,

validé

par

Les partenaires :
Les sociétés IXI et ELF Aquitaine Production d'une part; les laboratoires LaBRI et LADS

d'autre part.
AltaRica : phase II (de Novembre 1997 à Octobre 1999)
Objectifs :
Stabilisation du langage AltaRica, réalisation d'un prototype et méthodologie d'utilisation.
Résultats :
La sémantique du langage a été fixée. Des prototypes d'outils nécessaires à la
simulation d'un modèle AltaRica ont été développés. Des prototypes de compilateurs

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 9

vers les outils Aralia et Mec ont été développés et un premier manuel méthodologique a
été écrit.
Les partenaires :
La société d'ingénierie IXI, les industriels Dassault Aviation, ELF EP, Schneider Electric,
Renault, IPSN et Thomson Detexis, et enfin les laboratoires LaBRI et LADS.
AltaRica : phase III (de Juin 2001 à Mai 2003)
Objectifs :
Réalisation d'un atelier AltaRica
Les partenaires :
La société d'ingénierie IXI, les industriels Dassault Aviation, TotalFinaElf, Schneider
Electric, France Telecom, Thales systèmes aéroportés, et enfin les laboratoires LaBRI,
IRCCyN et ONERA.
Jusqu'à maintenant, on continue à développer des outils dans ce langage. Et un outil de
vérification basée sur le préfixe dans ce mémoire est un exemple.


2.2 Définition
Tout d'abord, on concerne le réseau de Petri, étant un des langages de modélisation en bas
niveau. Il est défini dans [Couvreur04] comme le suivant:
Définition 2.1 (Réseau de Petri)
Un réseau de Petri R est une structure <P, T, Pre, Post> où
•
•

P et T sont des ensembles (finis ou infinis) disjoints,
Pre et Post sont de fonctions de T dans IN|P| \ {0}.

Les éléments de P et T sont appelés des places et des transitions, et Pre et Post sont les
fonctions de pré- et post-conditions des transitions.
Un marquage m de R est un multi-ensembles de P (m ∈ IN|P|). Un réseau marqué <R, m0> est la
donnée d'un réseau de Petri R et d'un marquage initial m0.
Un réseau étiqueté <R, Σ, λ> est la donnée d'un réseau de Petri R, d'un alphabet fini Σ et d'une
fonction d'étiquetage sur les transitions λ: T → Σ.
L'ensemble des prédécesseurs (resp. des successeurs) d'une place p est défini par :
•p = { t ∈ T| Post (t) (p) ≠ 0} (resp. p• = { t ∈ T| Pre (t) (p) ≠ 0}).
L'ensemble des prédécesseurs (resp. des successeurs) d'une transition t est défini par :
•t = { p ∈ P| Pre (t) (p) ≠ 0} (resp. t• = { p ∈ P| Post (t) (p) ≠ 0}).
Si S est un ensemble de P ∪ T, alors *s (resp. s*) désigne l'ensemble de ses prédécesseurs
(resp. successeurs) directs et indirects. *s et s* sont défini par induction de la façon suivante:
s∈ *s ∧ ∀r ∈ P ∪ T , r• ∩ *s ≠ 0 → r ∈ *s
s∈ s* ∧ ∀r ∈ P ∪ T , •r ∩ s* ≠ 0 → r ∈ s*

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica


Page 10

Exemple 2.1
Réseau de Petri:
P = { p1, p2, ..., p7}
T = { t1, t2, ..., t7}
Pre (t1) = { p1 }
Post (t1) = { p2, p3 }
m0 = {p1}

p1
t1

t2

p2

p3

p4

t3

t4

t5

t6
p7


p6
t7
Figure 2.1: Réseau de Petri

Définition 2.2 (Règle de franchissement)
Soit R = <P, T, Pre, Post> un réseau de Petri. Soient t une transition et m un marquage de R.
Une transition t est franchissable à partir de m (noté par m[t>) si Pre(t) ≤ m. Franchir une
transition t à partir du marquage m amène au marquage m' (noté par m[t>m') défini par:
m' = m + Post(t) - Pre(t)
Nous notons Reach(R, m0) l'ensemble des marquages accessibles du réseau marqué <R, m0>.
On concerne le problème Solitaire Game avec n = 3 (SG(3)) dans [Arnold92].

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 11

Exemple 2.2
SG(3) en langage réseau de Petri:
P = { s0_s_B, ...}
T = { t1_1, ...}
Pre (t1_1) = { s0_s_B, s1_s_E }
Post (t1_1) = { s0_s_E, s1_s_B }
m0 = {s0_s_B, s1_s_E, s2_s_W}
...

Figure 2.2: Réseau de Petri de SG(3)


Réseau de Petri est facile à utiliser mais est difficile concevable de modéliser des systèmes très
complexes [Pagetti04].

L'AltaRica est un langage de modélisation en haut niveau. Il regroupe des variables (des états
du réseau de Petri) aux macro-états et des transitions aux macro-trasitions.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 12

La description d'un modèle AltaRica comprend les points suivants [Arnold03]:
1. La description de la hiérarchie du système.
2. La description des interfaces (visibilité) des composants.
3. La description des composants qui comprend :
o

Les variables d'état.

o

Les variables de flux.

o

Les événements et les transitions.


o

Les assertions qui lient ses flux et ses états.

4. La description des interactions entre les composants qui comprend :
o

Les assertions qui lient leurs flux et leurs états.

o

Les contraintes de synchronisation qui relient leurs événements.

o

Les priorités entre leurs événements.

5. La description des directifs outils afin d'orienter et/ou d'améliorer les compilations vers
les outils de calculs sur le modèle.
De part la multitude de concepts offerts dans le langage AltaRica, il est naturel de pouvoir
décrire par de nombreuses façons différentes un système donné. Il ne faut surtout pas percevoir
cela comme un défaut du langage, mais bien au contraire comme un de ses points forts.
AltaRica est en effet destiné à être utilisé dans des contextes différents, par des personnes
ayant des cultures différentes et avec des objectifs également différents.
Selon [Point00], un système est constitué de composants. Dans la terminologie AltaRica un
composant est situé au plus bas niveau dans la hiérarchie décrivant le système.
Définition 2.3a (Macro-état)
Les états d’un composant sont décrits de manière implicite par un ensemble de variables (des
états du réseau de Petri). Un état du composant est alors une évaluation de ces variables.
Par la suite nous désignerons par état d’un composant, une évaluation de ses variables d’états

et par configuration, l’association d’un état et d’une évaluation des variables de flux (ce qu'on ne
concerne pas encore dans ce mémoire).
Définition 2.3b (Macro-transition)
Les événements modifient l’état d’un composant; ces changements d’états sont appelés
transitions. Le langage permet une description implicite de l’ensemble des transitions d’un
composant par un ensemble de macro-transitions. Une macro-transition est de la forme
G(s,f) → e → s:= Succ(s, f)
où G(s, f) est une condition.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 13

Exemple 2.3
Macro-transition et des transitions correspondantes

garde

nom de
l'événement

|- e ->

0<= x <= 1

mise à jour


x:= x + 2;

e
x = 0

x = 2
e

x = 1

x = 3

Figure 2.3: Macro-transition et des transitions correspondantes

On utilise la notion e dans le programme AltaRica pour présenter qu'il n'y a pas de changement
dans le composant-là.
Exemple 2.4
SG(3) en langage AltaRica dans la figure 2.4.
Dans le vecteur de synchronisation t1, on a
<t1, s0.b0, s1.b1, s2.e >;

Il montre la synchronisation entre les composants s0 et s1.
Il n'y a pas de changement dans le composant s2.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

domain


Page 14

TypeSlot = {E, W, B};

node Slot
flow

s

// variable de flux
// variable d'état

: TypeSlot

state s_ : TypeSlot
event e, w1, b1, w, w0, b, b0;

// transitions du composant

trans
s_ = E

|- e

-> s_

:= E;

s_ = E


|- w1

-> s_

:= W;

s_ = E

|- b1

-> s_

:= B;

s_ = W

|- e

-> s_

:= W;

s_ = W

|- w

-> s_

:= W;


s_ = W

|- w0

-> s_

:= E;

s_ = B

|- e

-> s_

:= B;

s_ = B

|- b

-> s_

:= B;

s_ = B

|- b0

-> s_


:= E;

// assertion

assert s = s_;
edon
node Main
sub s0, s1, s2 : Slot;
event t1, t2, t3, t4, t5, t6;
trans
true |- t1,t2,t3,t4,t5,t6

-> ;

// vecteur de synchronisation

sync
<t1, s0.b0, s1.b1, s2.e >;
<t2, s0.e , s1.b0, s2.b1>;
<t3, s0.b0, s1.w , s2.b1>;
<t4, s0.w1, s1.w0, s2.e >;
<t5, s0.e , s1.w1, s2.w0>;
<t6, s0.w1, s1.b , s2.w0>;
extern initial_state =
s0.s_ = B,
s1.s_ = E,
s2.s_ = W;
edon


Figure 2.4: SG(3) en langage AltaRica

On peut trouver la syntaxe de langage AltaRica et autres exemples dans l'annexe.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 15

2.3 Transformation de l'AltaRica au réseau de Petri

On transforme le système modélisé en langage AltaRica au système représenté par le réseau
de Petri. Dans cette étape, on utilise la bibliothèque altatools de [Point00] pour analyser la
structure d’un programme AltaRica entré et pour créer un outil alta2net. Le format de
transformation de l'AltaRica au réseau de Petri est présenté dans la section 4.1.
On ne concerne que des variables d'états et ignore des variables de flux nécessaires pour la
vérification dans le temps prochain [Point00].
En suite, on peut utiliser le dépliage normal sur ce réseau de Petri (dans la section 3.2). C'est la
méthode la plus simple pour dépliage du modèle en langage AltaRica, mais elle a une
performance la moins efficace.
Les autres meilleures méthodes sont proposées dans les sections suivantes telles que le
dépliage de produits d'automates (dans la section 3.3), le dépliage basé sur le préfixe local
(dans la section 5.1), et les dépliages basés sur les techniques LCA et RMQ (dans la section 5.2
et 5.3).

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX



Dépliage du modèle en langage AltaRica

Page 16

3. Dépliage de réseau de Petri
Depuis longtemps, on cherche une structure plus simple pour présenter un réseau de Petri, en
conçervant leurs caractéristiques, c'est le réseau d'occurrence. McMillan a proposé un
algorithme de base pour déplier un réseau de Petri en 1995. Les autres améliorations sont
publiées dans les années suivantes.

3.1 Notions élémentaires
Notions élémentaires [Couvreur04]:
Le réseau d'occurrence est une structure plus simple pour présenter un réseau de Petri, en
conçervant leurs caractéristiques.
Définition 3.1 (Réseau d’occurrence)
Un réseau marqué <R, m0> est un réseau d'occurrence si
• R est un réseau élémentaire (si ∀p∈P, ∀t∈T, Pre(p)(t) ≤ 1 ∧ Post(p)(t) ≤ 1),
• ∀p∈P: |•p| +m0(p) = 1
• <R, m0> est quasi-vivant (si ∀t∈T, ∃ m ∈ Reach(m0): m[t>).
On a des relations entre des noeuds dans un réseau d'occurrence comme les suivantes:
Définition 3.2 (Causalité, conflit et concurrence)
Soient R un réseau d'occurrence et x, y ∈ P ∪ T.
• x précède y (noté x ≤ y) si x ∈*y
• x et y sont en conflit s'il existe deux transitions distinctes tx et ty telles que tx < x ∧ ty < y,
•tx ∩ •ty ≠ 0.
• x et y sont concurrents (noté x || y) si ¬(x ≤ y), ¬(y ≤ x), ¬(x et y en conflit).
Définition 3.3 (Configuration)
Soit R un réseau occurrence. Une configuration C de R est un sous-ensemble de transitions qui
n'est pas en conflit deux à deux, et clos par le bas: (*C ∩ T = C).
On a donc que chaque événement e a uniquement une configuration étant notée par [e].

Définition 3.4 (Processus arborescent)
Soit S = <B, E, In, Out> un réseau d'occurrence. Soit h un homomorphisme de réseau de S
dans <R, m0>. La paire <S,h> est un processus arborescent de <R, m0> si
∀e1, e2 ∈ E: (In(e1) = In(e2) ∧ h(e1) = h(e2)) ⇒ e1= e2
Définition 3.5 (Dépliage)
Soit <R, m0> un réseau marqué. Il existe un unique (à équivalence prêt) plus grand (au sens de
⊆) processus arborescent de <R, m0>. Ce processus arborescent est appelé le dépliage de m0>.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 17

Exemple 3.1
Le réseau d'ocurrence correspondant du réseau de Petri dans l'exemple 2.1

Conflit

p1
Causalité
t1

t2

p2

p3

p4

p5

t3

t4

t5

t6

p6

p7

p6

p7

t7

t7
Concurence

p1

p1

t1

t2

t1

t2

p2

p3

p4

p5

p2

p3

p4

p5

t3

t4

t5

t6

t3

t4

t5

t6

p6

p7

p6

p7

p6

p7

p6

p7

t7

t7

t7

t7

Figure 3.1: Réseau d'ocurrence

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 18

3.2 Etat de l'art
McMillan a proposé un algorithme de base [McMillan95] pour déplier un réseau de Petri en
1995. Il a dit que: "Ceci pour autant qu'il est vrai qu'il n'y a pas d'algorithme rapide pour générer
un préfixe".
Définition 3.6a (Préfixe fini [Couvreur04, Grivet01])
Un préfixe fini Cutoff de <S, h> est un sous-ensemble d'événements de S satisfaisant
• E \ Cutoff* est fini
• pour tout e, e' ∈ Cutoff, Il n'existe pas le cas où e ≤ e'.
Définition 3.6b (Préfixe fini complet)
Un préfixe fini Cutoff de <S, h> est complet si Reach(Cutoff) = Reach (R, m0).
Heljanko dans [Heljanko99] a démontré que le problème de l'extension d'un préfixe fini est NPcomplet.
Algorithme de base

void Unfolding::unfold()
{
for each Place p ∈ _lPlacesList
if

( p->getValue() = 1)

{
Condition b = Condition ( p, NULL

);

_lB->insert ( b );
generateTransition ( b );
}
while

( _lToDo->getSize() != 0)

{
Event e = _lToDo->pop();
generateConfiguration ( configuration, e );
if ( isCutOff (e) )

_lCut->insert(e);

else
{
_lE->insert(e);
for each

Place p ∈ lSuccessorsList(e)

{

Condition b = Condition ( p, e );
_lB->insert(b);
generateTransition ( b );
}
}
}
}

Figure 3.2a: Algorithme de dépliage

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 19

void Unfolding::generateTransition ( Condition b)
{
for each

Transition

t ∈ _lTransitionsList

if ( t->isPrePlace(sName) = 1)
{
ObjectsList lCoSetsList = findCoSetIterator ( t, b);
testCoSet(lCoSetsList,0);
if ( isExist( lCoSetsList ))

{
for each CoSet

c ∈ lCoSetsList

{
Event e = Event( t );
_lToDo->insert(e);
// ajouter ce pointer de e au ToDo
}
}
}
}

Figure 3.2b: Génération des transitions

Exemple 3.2
Le préfixe fini du réseau de Petri dans l'exemple 2.1.

p1
t1

t2

p2

p3

p4

p5

t3

t4

t5

t6

p6

p7

p6

p7

t7

t7

Figure 3.3: Préfixe fini

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 20

Les travaux de Khomenko et Koutny [Heljanko et al, 02] montrent que des améliorations
peuvent être faites dans le cas de réseaux de Petri concrets. Les autres améliorations sont
publiées dans les années suivantes. Esparza a proposé une amélioration [Esparza et al, 96]
sur l'ordre adéquat.
Car dès les premiers travaux sur les préfixes finis, McMillan a mis en évidence que la condition
∀e ∈ Cutoff , ∃ C ∈ Conf (Cutoff): h(Cut(e))= h(Cut(C))
n'est pas suffisante [Couvreur04].
Définition 3.7 (Ordre adéquat)
Un ordre partiel ≤ sur les configurations d'un dépliage <S, h> est un ordre adéquat si:
• ≤ raffine ⊆
• ≤ est bien fondé (i.e. il n'existe pas de suite infinie strictement décroissant).
• ≤ est compatible avec l'extension: pour toute transition t, pour toutes les configurations
C1, C2 de S telles que h(Cut(C1)) = h(Cut(C1))
C1 < C2 ⇒ ∀C2 ∈ C2.t, ∀C1 ∈ C1.t : C'1 < C'2
Dans ce mémoire on n'utilise qu'un ordre adéquat SizeParikhLex. Cet ordre adéquat consacre la
taille et la lexicographique de la configuration. Il y a encore des autres ordres adéquats qui sont
analysés et testés dans [Grivet01].
Exemple 3.3
Le préfixe du dépliage de SG(3).

Figure 3.4: Préfixe du dépliage de SG(3)

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 21

3.3 Dépliage de produits d'automates
Dans quelques cas spéciaux, on a des algorithmes plus efficaces tels que le cas de dépliage de
produits d'automate [Esparza et al, 99]. On peut appliquer cet algorithme pour déplier un
réseau de Petri transformé à partir du langage AltaRica. On doit déplier localement sur chaque
composant ainsi que déplier globalement en utilisant les résultats locaux.

Dépliages locaux
Dans chaque composant, on n’a qu’un seul état initial. Donc le processus d’arborescent est un
arbre. Autrement dit, le dépliage d’une machine à états est simplement un arbre. Les conditions
et les événements sont identifiés par des séquences de transitions de la machine
[Couvreur04].
L'ordre adéquat local est comme dans la définition 3.7.
Le test du conflit entre deux événements est comme le suivant:
Définition 3.8 (Conflit)
Les événements e1 et e2 sont en conflit ssi :
• depth ( e1 ) = depth ( e2 ) et e1 ≠ e2
• depth ( e1 ) > depth ( e2 ) et precedent ( e1 ) et e2 sont en conflit
• depth ( e1 ) < depth ( e2 ) et precedent(e2) et e1 sont en conflit
Autrement dit, dans la même profondeur, test du conflit si deux événements sont différents. Si
les événements sont dans les différentes profondeurs, il faut sauter à l'événement précédent.
On trouve que dans le dépliage de produits d'automate, le test du conflit entre deux événements
a une complexité O(h). De plus, on va diminuer cette complexité à O(h1/2) ou jusqu'à une
constance dans la section 5.
Le dépliage local en détail est très simple comme dans l'annexe.

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 22

Exemple 3.4
On a trois composants locaux s0, s1 et s2 comme dans la figure 3.5:

B

t1_b0

t3_b0
E

t4_w1

t6_w1

W
Figure 3.5a: Composant s0 de SG(3)

E

t4_w0

ta

t1_b1

t5_w1

W

t2_b0

B
t3_w

Figure 3.5b: Composant s1 de SG(3)

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX

t6_b


Dépliage du modèle en langage AltaRica

Page 23

W

t5_w0

t6 _w0
E

t3_b1

t2_b1

B
Figure 3.5c: Composant s2 de SG(3)

Son dépliage local dans la figure 3.6 :
Processus arborescent fini correspondant du composant s0.

B
Conflit

t1_b0

_t3_b0

E'
t4_w1

W1

E''
t6_w1

W2

t4_w1

W3

t6_w1

W4

Figure 3.6a: Processus arborescent dans le composant s0 de SG(3)

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX


Dépliage du modèle en langage AltaRica

Page 24

Processus arborescent infini correspondant du composant s1.

E

t5_w1
W

h
hauteur
global

t1_b1
B

t4_w0

t2_b0
W’

B’

E’

E’’

…
Figure 3.6b: Processus arborescent dans le composant s1 de SG(3)

Processus arborescent fini correspondant du composant s2.

W

t5_w0

_t6_w0

E'

E''
t2_b1

t3_b1

B1

B2

t3_b1

B3

t2_b1

B4

Figure 3.6c: Processus arborescent dans le composant s2 de SG(3)

Mémoire de fin d'études de NGUYEN Duy Tung, Promotion IX