thesis

Le calcul d'invariants dans les réseaux de Pétri à prédicats transitions unaires

Defense date:

Jan. 1, 1986

Edit

Institution:

Paris 11

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

Combinatorial explosion problems often arise at the time of the design or the analysis of Petri nets. To increase this combinatory, some abbreviations of the formalism have been introduced in the literature, especially the Unary Predicate/Transition nets. The flows whose definition has been extended to this model provide invariant properties about the "structure" of a Petri net that is independent of any initial marking. Their computation uses algorithms based on finding solutions to linear systems of equations in integers or positive integers. Some of these algorithms are exponential and searching heuristics in order to decrease their cost is a part of this work. It is shown that these heuristics lead sometimes to notable improvements of the performances and allow, thanks to the data structure implemented within the algorithms, the analysis of sizeable nets. The purpose of this thesis concerns also the integration of these algorithms within an overall program which is conceived in an extendable way, made up of a graphical editor and of other tools for the analysis of Petri nets.

Abstract FR:

L'écriture ou l'analyse d'un réseau de Petri pose souvent des problèmes d'explosion combinatoire. Pour diminuer cette combinatoire des abréviations du formalisme ont été introduites dans la littérature, en particulier les réseaux à Prédicats/Transitions­Unaires (RPTU). Les semi-flots dont la définition a été étendue à ce modèle permettent d'établir des propriétés invariantes sur la "structure" d'un réseau de Petri, c'est à dire indépendantes d'un marquage initial. Leur détermination a lieu à l'aide d’algorithmes basés sur la recherche de solutions entières ou entières positives de systèmes linéaires d'équations. Certains de ces algorithmes sont exponentiels et nous nous intéressons à la recherche d'heuristiques pouvant abaisser cette complexité. Nous montrons que ces heuristiques entraînent dans certains cas des améliorations remarquables des performances et permettent aussi, grâce à la structure des données gérée au sein des algorithmes, l'analyse de réseaux de taille importante. Ce travail concerne également l'intégration de ces algorithmes dans un outil logiciel plus général conçu de façon extensible, comportant un éditeur graphique ainsi que d'autres outils d'analyse de réseaux de Petri.