Les réseaux de Petri : modèles fondamentaux

Michel Diaz

Description

Cet ouvrage répond au besoin de disposer d'un ensemble complet de connaissances et méthodes nécessaires à la maîtrise des systèmes technologiques. Il présente aussi bien les aspects fondamentaux qu'expérimentaux. Les savoirs, théories et méthodes rassemblés ici, ont été choisis pour leur pertinence dans l'avancée des connaissances ou pour la qualité des résultats obtenus dans le cas d'expérimentations réelles.

Introduction. Les réseaux de Petri places-transitions. Les réseaux de Petri et la modélisation du temps. Les abréviations des réseaux de Petri. Les réseaux de Petri à distributions.

Sujets

• Automatique
• Robotique

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 11 mai 2001
• Nombre de lectures: 280
• EAN13: 9782746241763
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

INFORM ATIQU E INFORM ATIQU ETraité IC2 Information – Commande – Communication
E T SYSTÈME S E T SYSTÈME S
Le traité Information, Commande, Communication répondD ’ICINFORM A2TIO N D ’ICINFORM A2TIO N
au besoin de disposer d’un ensemble complet des
connaissances et méthodes nécessaires à la maîtrise des
I n f ormati o n – C omma n d e – C o mmuI nnif ocatrmati i o no n – C omma n d e – C o mmunicat i o n
Conçu volontairement dans un esprit d’échange disciplinaire, le
traité IC2 est l’état de l’art dans les domaines suivants retenus
Traitement du signal et de l’image
Informatique et systèmes d’information Les réseaux
Systèmes automatisés et productique Vérification et
Management et gestion des STICS
Cognition et traitement de l’information. de Pétri
mise en œuvre desChaque ouvrage présente aussi bien les aspects
fondamentaux qu’expérimentaux. Une classification des
Modèles fondamentauxdifférents articles contenus dans chacun, une bibliographie et
un index détaillé orientent le lecteur vers ses points d’intérêt réseaux de Pétriimmédiats : celui-ci dispose ainsi d’un guide pour ses
Les savoirs, théories et méthodes rassemblés dans chaque
ouvrage ont été choisis pour leur pertinence dans l’avancée
des connaissances ou pour la qualité des résultats obtenus
dans le cas d’expérimentations réelles.
sous la direction de
Michel Diaz
978-2-7462-1180-3
9:HSMHOG=WVV]UX:
www.hermes-science.com
Vangelis Th. Paschos
Optimisation combinatoire 4 Les réseaux de Petri© Hermes science europe Ltd, 2001
Hermes science P ublications
8, quai du marché-Neuf
75004 Paris
serveur web : http://www.hermes-science.com
IsBN 2-7462-0250-6
Catalogage electre-Bibliographie
Diaz, michel (sous la direction de)
Les réseaux de Petri – Modèles fondamentaux
Paris, Hermès science Publications, 2001
IsBN 2-7462-0250-6
rAmeAU : Petri, réseaux de
DeWeY : 515 : Analyse mathématique
005.1 : Programmation. Programmes. Logiciels.
Principes de la programmation
Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une
part, que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.Les réseaux de Petri
Modèles fondamentaux
sous la direction de
michel DiazIl a été tiré de cet ouvrage
20 exemplaires hors commerce réservés
aux membres du comité scientifique,
aux auteurs et à l’éditeur
numérotés de 1 à 20a
m
m
t
y
d
o
n
f
o
n
m
e
t
m
s
n
n
r
o
u
n
e
m
é
m
a
o
t
n
s
o
s
n
è
f
e
o
r
r
f
m
n
a
o
t
m
t
t
q
o
u
t
e
r
a
a
a
Les réseaux de Petri
sous la direction de Michel Diaz
fait partie de la série I I d’I I
dirigée par Jean-Charles Pomerol
t I IC2 I I – C – C I C I
sous la direction scientifique de Bernard Dubuisson
Le traité Information, Commande, Communication répond au besoin
de disposer d'un ensemble complet des connaissances et méthodes
nécessaires à la maîtrise des systèmes technologiques.
Conçu volontairement dans un esprit d'échange disciplinaire, le traité IC2
est l'état de l'art dans les domaines suivants retenus par le comité
scientifique :
réseaux et télécoms
Traitement du signal et de l'image
Informatique et systèmes d'information
systèmes automatisés
Productique
Chaque ouvrage présente aussi bien les aspects fondamentaux
qu'expérimentaux. Une classification des différents articles contenus
dans chacun, une bibliographie et un index détaillé orientent le lecteur
vers ses points d'intérêt immédiats : celui-ci dispose ainsi d'un guide pour
ses réflexions ou pour ses choix.
Les savoirs, théories et méthodes rassemblés dans chaque ouvrage ont
été choisis pour leur pertinence dans l'avancée des connaissances ou pour
la qualité des résultats obtenus dans le cas d'expérimentations réelles.r
t
a
d
a
e
r
t
d
a
d
a
l
o
e
h
r
o
d
m
a
n
a
e
y
u
r
r
a
e
u
a
e
n
o
é
a
e
d
r
z
y
t
e
u
t
r
a
x
Liste des auteurs
Bernard B I
LAAs-CNrs
Toulouse
marc B
LAAs-CNrs
Toulouse
michel d I
LAAs-CNrs
Toulouse
Claude GI
LIP6
Université Pierre et marie Curie
Paris
serge h
LAmsADe
Université Paris-Dauphine
Patrice m
LAmsADe , Université Paris-Dauphine
LerI-resYCOm , université de reims Champagne-Ardenne
Jean-François P -P
CeDrIC
Conservatoire national des arts et métiers
Paris
Patrick s C
ecole nationale supérieure d’ingénieurs de constructions aéronautiques
LAAs-CNrs
Toulouse
François V
Institut national des sciences appliquées
LAAs-CNrs
ToulouseTable des matières
Avant-propos 17
Michel DIAZ
Introduction9
Michel DIAZ
La conception et la spécification 1
Le choix du modèle 21
Les réseaux de Petri2
Les différentes familles de réseaux de Petri3
Plan des deux ouvrages6
Notations générales
Ensembles et nombres 29
Vecteurs et matrices
Séquences et langages 30
Réseaux de Petri
PREMIÈRE PARTIE. LE S RÉSEAUX DE PETRI PLACES-TRANSITIONS 33
Chapitre 1. La sémantique de base5
Michel DIAZ
1.1. Rappels sur les automates et les machines à états 3
1.1.1. Modèle de base 3
1.1.2. Le cas particulier des tâches et des processus7
1.1.3. La modélisation
1.2. Des machines à états aux réseaux de Petri 38
1.2.1. La composition des machines à états10 Les réseaux de Petri
1.2.2. Le motif de base 39
1.2.3. Composition et synchronisation 40
1.3. Concepts et définitions1
1.3.1. Les états locaux et la sensibilisation2
1.3.2. Définition de la sémantique du parallélisme3
1.3.2.1. Le problèmee
1.3.2.2. Le choix classique de nombreux modèles :
l'entrelacement 4
1.3.3. Tir des transitions4
1.4. Graphe d'accessibilité ou graphe des marquages 45
1.5. Quelques modèles de spécification de base8
1.5.1. Lancement parallèle (co-begin) et terminaison synchronisée
(co-end)
1.5.2. Synchronisation par signal
1.5.3. Exclusion mutuelle9
1.5.4. Lecteurs-écrivains 51
1.5.5. Tampon borné3
1.6. Conclusion
1.7. Bibliographie4
Chapitre 2. Application des réseaux de Petri aux protocoles
de communication 57
Michel DIAZ
2.1. Les modèles de base
2.2. Une ouverture simple de connexion 59
2.2.1. Les différentes sémantiques du couple émission-réception 5
2.2.2. Lesss globales 60
2.2.3. Conclusion 6
2.3. Le bit alterné (BA ) : modèle et validation2
2.3.1. Perte de messages3
2.3.2. Modélisation en présence de pertes4
2.4. Automates communicants et réseaux de Petri6
2.5. Conclusion
2.6. Bibliographie7
Chapitre 3. Méthodes d'analyse des réseaux de Petri 69
Serge HADDA D et François VERNADAT
3.1. Introduction 6
3.2. Analyse comportementale des réseaux de Petri 71
3.2.1. Sémantiques d'un réseau 7
3.2.2. Propriétés usuelles2
3.2.2.1. Définition des propriétésTable des matières 11
3.2.2.2. Relations entre propriétés 74
3.2.2.3. Monotonie dess5
3.2.2.4. Caractérisation des propriétés à l'aide d'un graphe
d'accessibilité fini6
3.2.2.5.n des propriétés à l'aide de séquences
finies particulières 78
3.3. Analyse des réseaux par les invariants linéaires 80
3.3.1. Définitions et premières applications
3.3.2. Calcul de flots4
3.3.3.l de semiflots 86
3.3.4. Application des invariants à l'étude d'un réseau9
3.3.4.1. Modélisation du problème lecteurs/écrivains 90
3.3.4.2. Vérification des contraintes de synchronisation1
3.3.4.3. Discussion 93
3.4. Réductions de réseaux4
3.4.1. Préagglomération de transitions5
3.4.2. Postagglomération des7
3.4.3. Suppression de place implicite8
3.5. Le « graphe » réseau de Petri9
3.5.1. Résultats généraux 100
3.5.2. Machines à états
3.5.3. Graphes d'événements 104
3.5.4. Réseaux à choix libre
3.6. Conclusion 115
3.7. Bibliographie6
Chapitre 4. Décidabilité et complexité de problèmes de réseaux de Petri. . 119
Serge HADDAD
4.1. Introduction9
4.2. Rappels de décidabilité et de complexité 121
4.3. Résultats théoriques à propos du graphe d'accessibilité 124
4.4. Analyse des réseaux de Petri non bornés7
4.4.1. Construction du graphe de couverture8
4.4.2. Plus courtes séquences 134
4.4.3. Analyse rétrograde 13
4.5. Le problème de l'accessibilité
4.5.1. Une condition nécessaire d'accessibilité 140
4.5.2. Unen suffisanteé
4.6. Extensions de réseaux de Petri 143
4.6.1. Les réseaux à arcs inhibiteurs
4.6.2. Lesx automodifiants5
4.6.3. Les réseaux récursifs7 12 Les réseaux de Petri
4.7. Langages de réseaux de Petri 151
4.8. Conclusion6
4.9. Bibliographie
DEUXIÈME PARTIE. LE S RÉSEAUX DE PETRI ET LA MODÉLISATION DU TEMP S . 159
Chapitre 5. Les réseaux de Petri temporels 16
Bernard BERTHOMIEU, Marc BOYER et Michel DIAZ
5.1. Introduction 161
5.2. Réseaux de Petri temporels 164
5.2.1. Réseauxs4
5.2.2. Etats et règle de tir5
5.2.3. Ensemble des états et échéanciers6
5.2.4. Domaines de tir7
5.3. Caractérisation du comportement et méthode des classes d'états 169
5.3.1. Classes d'états 16
5.3.2. Transitions entre classes d'états
5.3.3. Egalité des classes d'états 172
5.3.4. Graphe dess
5.3.5.e des marquages et graphe des classes 17
5.4. Analyse et exploitation du graphe des classes d'états6
5.4.1. Analyse du comportement des systèmes temporels
5.4.2. Accessibilité d'un marquage7
5.4.3. Propriété borné
5.4.4. Propriétés spécifiques de l'ensemble des marquages
ou des séquences de tir 181
5.4.5. Analyses temporelles et existence d'échéanciers 18
5.5. Un exemple d'application2
5.6. Extensions et variations6
5.6.1. Interprétation des transitions multisensibilisées
5.6.1.1. Sensibilisations multiples 18
5.6.1.2. Choix de la transition tirable8
5.6.1.3. Choix des transitions sortantes en cas de conflits 188
5.6.1.4. Règle de tir étendue9
5.6.1.5. Propriété borné
5.6.1.6. Alternatives 191
5.6.2. Autres ext