Les Symétries dans les Réseaux de Petri Stochastiques (RdPS) Construction du Graphe Symbolique

¹ Institut d'Informatique, USTHB, BP. 32, EL-Alia, Algerie.
² Universite de Blida, Algerie.

Received: December 1997

Abstract

The main purpose of this paper is to give a method for construction of the reduced reachability graph for Stochastic Petri Nets (SPN), the symbolic graph. This construction is achieved by exploiting the structural symetries in the net using the theory of bisimulation of places for detecting isomorphic parts in the net. The symbolic graph, being isomorphic to an agregated Markov chain, may be used to prove qualitative properties as liveness, boundness, ... Moreover, this reduced graph make more easy the computation of the performance measures of interest as the mean number of tokens in a place, the mean number of firing transition ... We have so developped a tool, SSPN (Stochastic Symetric Petri nets), for generating the symbolic graph and deducing qualitatives and quantitatives properties.

Résumé

L'analyse d'un réseau de Petri nécessite souvent le développement du graphe des marquages accessibles (GMA), dont la taille rend généralement son étude impossible. Le but de notre article est de proposer une méthode de construction d'un graphe réduit pour les réseaux de Petri stochastiques possédant des propriétés de symétrie, le graphe des marquages symboliques (GMS), en nous inspirant du principe de la théorie de la bisimulation de places. Cette construction s'effectue de manière automatique, en détectant les symétries structurelles du réseau. Nous montrons que ce graphe peut être utilisé pour déduire certaines propriétés du réseau, telles que la vivacité, la bornitude... De plus, le GMS étant isomorphe à la chaîne de Markov agrégée du GMA, nous pouvons alors déduire les paramètres de performances du réseau. Nous avons développé un outil, SSPN (Stochastic Symetric Petri Nets), permettant de générer le GMS et de déduire les propriétés qualitatives et quantitatives d'un RdPS.