Dissertations / Theses: 'Réseaux de Petri Lots'

1

Caradec, Muriel. "Modélisation des systèmes de production à haute cadence multiproduits par réseau de Petri lots colorés." Montpellier 2, 1998. http://www.theses.fr/1998MON20118.

Full text

Abstract:

Les systemes de production a haute cadence actuels doivent s'adapter a des commandes successives de produits differents (multiproduits) en quantites limitees. Ces systemes sont souvent composes de machines separees par des convoyeurs qui jouent le role a la fois de transfert et de stock tampon. Ils sont hybrides, car ils mettent en jeu des modeles continus et discontinus. Les parties continues correspondent soit a des produits evalues et consommes de facon continue, soit a des deplacements de produits discrets sur les convoyeurs. L'objectif de ces travaux etait de determiner un outil de modelisation dedie aux systemes de production a haute cadence multiproduits. Il avait ete defini ulterieurement un modele hybride dedie aux systemes monoproduit, le reseau de petri lot. Afin de beneficier des avantages de ce modele monoproduit deja existant, nous avons donc defini une extension utilisant la couleur. Cette nouvelle notion permet d'identifier la matiere circulant dans une chaine (par unite ou par lot) et de prendre en compte la multiplicite des produits. Ce nouveau modele s'appelle reseau de petri lots colore. Un modele generique des systemes de convoyage est presente : le transporteur colore virtuel (tcv). Les differents phenomenes observes lorsque deux lots colores rentrent en contact sur un tcv sont egalement analyses. Nous proposons ensuite une etude sur les conflits transitions et couleurs rencontres dans notre modele. Enfin, une partie est consacree a l'application du modele monoproduit a la simulation des chaine de production a haute cadence.

APA, Harvard, Vancouver, ISO, and other styles

2

Mnassri, Radhia. "Réseaux de Petri Lots Triangulaires pour la modélisation mésoscopique et l'étude de la congestion dans le trafic routier." Thesis, Aix-Marseille, 2015. http://www.theses.fr/2015AIXM4376.

Full text

Abstract:

L'usage excessif des routes peut entraîner de nombreux inconvénients dont la pollution, les accidents et la congestion. Une solution accessible à court terme consiste à mettre en œuvre des systèmes de gestion de trafic. Dans ce cadre, nous proposons un formalisme, appelé Réseaux de Petri Lots Triangulaire, qui permet la modélisation et la simulation du trafic routier au niveau mésoscopique comme un système à événements discrets. Le RdPLots Triangulaire permet ainsi de décrire les caractéristiques globales du trafic routier: flux, densité et vitesse à travers la proposition d'une relation flux-densité triangulaire. Cette relation implique une modification de la dynamique des lots. Cette dynamique permet maintenant de représenter les deux états du trafic routier à savoir fluide et congestionné ainsi que les trois régimes dédiés au comportement libre, congestion et décongestion. Le calcul des flux instantanés des transitions est à présent réalisé par une méthode basée sur la technique de programmation linéaire en ajoutant une contrainte qui prend en compte l'état et le régime des lots. Pour modéliser des stratégies de contrôle telles que la variation de la vitesse limite (VSL), nous avons intégré au RdPLots Triangulaire des événements contrôlés qui permettent le changement de la vitesse maximale d'une place lot et le flux maximal d'une transition continue ou lot. Tous ces apports théoriques sont implémentés dans un logiciel que nous avons appelé SimuleauTri, sous lequel nous avons étudié des portions d'autoroute à partir des données réelles. Les résultats de simulation sont proches des mesures effectuées sur le terrain, et montrent la pertinence de RdPLots Triangulaire
The excessive use of roads can cause many adverse effects including pollution, insecurity and congestion. The available short-term solution is the implementation of traffic management systems which optimize the flow and reduce congestion without needing additional infrastructures. In this context, we proposed a new formalism, called Triangular Batches Petri Nets (Triangular BPN), which combines modeling and simulation of traffic in mesoscopic level as a discrete event system. The Triangular BPN describing the overall characteristics of the road traffic such as flow, density, speed by representing a new triangular relation flow-density. This relation implies the modification of batches dynamic, which is now used to represent the two road traffic states : fluid and congested, as well as the three behaviors :free, congestion and decongestion. The calculation of the instantaneous firing flows is achieved by adding a constraint that takes into account the state and behavior of batches. A set of controlled events integrated to the Triangular BPN, that allow the variation of the maximum speed of batch place and the maximum flow of batch and continuous transition. These controlled events used to model the control strategies, such as variable speed limit (VSL). All these theoretical contributions implemented in a software that is called SimuleauTri and used to study a motorway portions from real data. The simulation results are close to the measurements on the ground and show the pertinence of Triangular BPN

APA, Harvard, Vancouver, ISO, and other styles

3

Kaakai, Fateh. "Modélisation et évalution des pôles d'échanges multimodaux : une approche hybride multiéchelle basée sur les réseaux Pétri Lots." Besançon, 2007. http://www.theses.fr/2007BESA2038.

Full text

Abstract:

Les pôles d'échanges multimodaux (PEM) constituent aujourd'hui la vitrine des réseaux de transport. C'est un système de transport complexe dont le bon fonctionnement conditionne celui du réseau de transport dans son ensemble. Dans le but de prévenir, de réduire ou si possible d'éviter les dysfonctionnements, les incidents et les accidents qui affectent quotidiennement un grand nombre de sites en exploitation, et qui, par ricochet, détériorent l'image et l'attractivité des transports collectifs en général, il devient nécessaire de systématiser l'évaluation à priori et à posteriori des performances des PEM comme cela s'est fait avec succès dans d'autres domaines, tels que celui des systèmes industriels de production. Ainsi, l'objectif de ces travaux de recherche est d'élaborer un modèle de simulation pour la mesure d'un certain nombre d'indicateurs quantitatifs de performance dédiés aux PEM. Le modèle de simulation proposé est basé sur les réseaux de Petri Lots, une extension des réseaux de Pétri Hybrides particulièrement adaptée pour la modélisation des systèmes multiéchelles complexes. Ce paradigme de modélisation offre, en outre, des techniques d'analyse formelle pour la vérification et la commande du modèle élaboré. Le modèle de simulation proposé sera utile poour définir et programmer à court terme des opérations de maintenance dans le but de prévenir des dysfonctionnements latents ou probables. Concernant les projets de PEM en cours de réalisation, il permettra d'éclairer les choix préalables à la conception des différentes composantes de ces sites en assistant les concepteurs dans les procédures de dimensionnement et de planification
A Multimodal Hub is a complex transportation system which has the role to interconnect several public and private transportation modes in order to promote intermodality practice. Because of many observed problems (such as recurrent congestion phenomena inside stations, high transfer times, long queues in front of services, etc. ) which contribute to deteriorate the image of public transport in general, it becomes more and more important for transit authorities to be able to perform many performance measures for identifying the causes of these problems and trying to find solutions. The main goal of the PhD thesis is to propose a simulation model for evaluating the main performance factors of multimodal transportation hubs. Among the most important quantitative factors, we can mention occupancy rates, queue lengths, mean service times, evacuation times, and measures related to intermodality practice such as connection times and waiting times. The suggested simulation model is based on Batches Petri nets which are an extension of Hybrid Petri nets. This paradigm is suitable for our study because it offers a multiscale modular modeling approach which allows mastering the complexity of the studied system. Besides, it offers formal analysis techniques for checking and design (control) purposes. This simulation model can be successfully used for (i) evaluating existing multimodal hubs, (ii) validating design projects of new multimodal hubs, and (iii) assisting designers during sizing and planning procedures

APA, Harvard, Vancouver, ISO, and other styles

4

Sadani, Tarek. "Vers l'utilisation des réseaux de Petri temporels étendus pour la vérification de systèmes temp-réel décrits en RT-LOTOS." Toulouse, INPT, 2007. http://ethesis.inp-toulouse.fr/archive/00000460/.

Full text

Abstract:

Cette thèse porte sur la vérification formelle de systèmes temps réel et procède par transformation de modèle entre l'algèbre de processus temporisée RT-LOTOS et les réseaux de Petri temporels étendus par des chronomètres et des données. Des schémas de traduction de RT-LOTOS vers ces réseaux de Petri étendus sont proposés et formellent prouvés. L'approche transformationnelle développée pour la partie "contrôle" de RT-LOTOS est étendue à la partie "données". Le langage RT-LOTOS est lui-même enrichi d'un opérateur de suspension/reprise qui permet de modéliser et vérifier une classe plus large de systèmes temps réel. Plusieurs études de cas attestent de l'efficacité des schémas de traduction proposés par rapport à des outils LOTOS ou RT-LOTOS développés antérieurement. L'approche proposée s'avère transposable à d'autres langages de modélisation, en particulier le profil UML temp réel TURTLE (Time UML and RT-LOTOS Environment)
This thesis investigates a transformational approach for the verification of Real-Time systems. The main objective is to reuse several verification techniques and tools originally developed for Time Petri nets for the profit of the timed process algebra RT-LOTOS. A set of translation patterns from RT-LOTOS to Time Petri nets extended with stowatches and data is proposed and formally proved. The RT-LOTOS language is extended with a suspend/resume operator, which allows the description of complex reactive systems whose temporal evolution can be suspended and then resumed at the same point. The efficiency of the new approach is demonstrated on various case studies. This work is not limited to the verification of real-time systems specified in RT-LOTOS. The approach provides a more powerful verification environment for real-time systems modelled in TURTLE, a real-time UML profile

APA, Harvard, Vancouver, ISO, and other styles

5

Sadani, Tarek. "Vers l'utilisation des réseaux de Petri temporels étendus pour la vérification de systèmes temps-réel décrits en RT-LOTOS." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2007. http://tel.archives-ouvertes.fr/tel-00149426.

Full text

Abstract:

Cette thèse porte sur la vérification formelle de systèmes temps réel et procède par transformation de modèle entre l'algèbre de processus temporisée RT-LOTOS et les réseaux de Petri temporels étendus par des chronomètres et des données. Des schémas de traduction de RT-LOTOS vers ces réseaux de Petri étendus sont proposés et formellement prouvés. L'approche transformationnelle développée pour la partie " contrôle " de RT-LOTOS est étendue à la partie " données ". Le langage RT-LOTOS est lui même enrichi d'un opérateur de suspension reprise qui permet de modéliser et vérifier une classe plus large de systèmes temps réel Plusieurs études de cas attestent de l'efficacité des schémas de traduction proposés par rapport à des outils LOTOS ou RT-LOTOS développés antérieurement. L'approche proposée s'avère transposable à d'autres langages de modélisation en particulier le profil UML temps réel TURTLE (Timed UML and RT-LOTOS Environment).

APA, Harvard, Vancouver, ISO, and other styles

6

Wu, Jia. "Utilisation de la conduite coopérative pour la régulation de trafic dans une intersection." Phd thesis, Université de Technologie de Belfort-Montbeliard, 2011. http://tel.archives-ouvertes.fr/tel-00703165.

Full text

Abstract:

L'objectif de ce travail est d'exploiter les potentialités offertes par la conduite coopérative afin de fluidifier le trafic au niveau des intersections isolées. Pour ce faire, nous avons proposé un nouveau système de régulation au sein des intersections en s'inspirant du principe de l'intersection autonome. Nous avons appelé notre système : SVAC (système du véhicule-actionneur coopératif). Il repose sur la possibilité des échanges d'information entre le véhicule et son environnement de conduite.Le SVAC permet une régulation plus précise du trafic puisqu'il se base sur les requêtes de droit de passage envoyées par les véhicules réellement présents dans l'intersection. En outre, grâce à la signalisation à bord, la régulation consiste à définir les séquences de passage des véhicules, ce qui permet de personnaliser la signalisation. Le gain de précision soulève plusieurs obstacles. D'une part, nous nous heurtons systématiquement à l'absence de modèles mathématiques permettant d'aborder le problème. D'autre part, la simple énumération des séquences implique une explosion combinatoire, ce qui ne convient pas à l'application temps-réelle de la régulation des intersections. Pour s'affranchir des deux problématiques nous avons utilisé les réseaux de Petri P-temporisés. Le modèle nous a permis de décrire sous la forme d'équations mathématiques les compteurs des différents évènements observés par les véhicules. Deux objectifs de régulation ont été dégagés après avoir déduit le temps moyen d'attente basé sur la formule de Little. Le premier consiste à vider les intersections au plus tôt. Nous avons proposé un algorithme de programmation dynamique et deux heuristiques. La première heuristique est directement issue de l'analyse des propriétés du problème posé. La deuxième est basée sur l'algorithme de colonies de fourmis. En effet, le problème défini est un cas particulier du problème du voyageur de commerce. Le deuxième objectif de régulation consiste à minimiser instantanément la longueur de la file d'attente. Dans ce cadre, nous avons supposé le fonctionnement à vitesse maximale du réseau de Petri. L'utilisation des contraintes sur les ressources nous a permis de définir des règles simples de régulation en utilisant le mapping.Dans ce mémoire, nous avons utilisé la simulation microscopique basée sur les lois de poursuite pour s'approcher du comportement de conduite. La simulation a servi pour la comparaison des différentes approches proposées dans ce mémoire avec les régulateurs adaptatifs et les intersections autonomes. Dans tous les cas notre approche se distingue par un gain de capacité, ce qui nous a encouragé de reproduire le SVAC à travers un prototype de robots. Cette maquette montre la faisabilité du système au moins pour des applications industrielles.

APA, Harvard, Vancouver, ISO, and other styles

7

Henry, Sébastien. "Synthèse de Lois de commande pour la configuration et la reconfiguration des systèmes industriels complexes." Phd thesis, Grenoble INPG, 2005. http://tel.archives-ouvertes.fr/tel-00168412.

Full text

Abstract:

le travail présenté dans ce mémoire de thèse apporte sa contribution à la synthèse de
lois de commande en contexte incertain des systèmes automatisés de production. L'incertain est ici
caractérisé d'une part par les variations imprévues des demandes client, mais également par les aléas
de fonctionnement déclarés au niveau de la partie opérative. L'approche, localisée au niveau 1 du
CIM, et en particulier au sein des modules de coordination des chaînes fonctionnelles, s'intègre au
sein d'un système plus général de Supervision, Surveillance et Commande. L'approche se distingue en
considérant la globalité du processus qui mène à la reconguration des lois de commande. En eet,
elle propose non seulement une méthode de modélisation de la partie opérative utilisant un formalisme
particulièrement adapté à la complexité des procédés considérés mais aussi une technique de synthèse
de lois de commande basée sur un mécanisme de recherche de chemins dans un graphe. La modélisation
proposée, proche de celle utilisée en planication automatique, est basée sur un ensemble d'opérations
qui décrivent la dynamique des chaînes fonctionnelles et leurs eets sur le ux de produits tout en
prenant en considération les contraintes sécuritaires et environnementales associées. Toute l'originalité
du mécanisme de synthèse proposé réside dans le compromis réalisé entre la complexité du graphe
manipulé et les performances de la solution obtenue.
Un exemple d'application basé sur un processus manufacturier réel, la plate-forme SAPHIR du
Laboratoire d'Automatique de Grenoble, et sur l'atelier logiciel développé sur la base du mécanisme
de synthèse proposé illustre les apports de notre approche.

APA, Harvard, Vancouver, ISO, and other styles

8

Sanogo, Alfred. "Méthodologie de conception des modèles exprimés en réseaux Petri : Raffinement des réseaux de Petri colorés." Paris 13, 2012. http://www.theses.fr/2012PA132051.

Full text

Abstract:

Les réseaux de Petri colorés sont très utilisés comme langage de spécification des systèmes complexes caractérisés par la concurrence. La spécification d'un système complexe (réel) nécessite généralement la prise en compte de nombreux détails. Des difficultés apparaissent lorsque l'on essaye de prendre en compte tous ces détails dans le modèle en une seule étape. L'une des solutions consiste à construire un modèle plus abstrait (avec moins de détails) et modifier ce modèle étape par étape en apportant plus de détails à chaque étape. Cette démarche appelée raffinement prend fin lorsque tous les détails sont pris en compte. Plusieurs chercheurs ont travaillé sur le raffinement des modèles exprimés en réseaux de Petri colorés et proposé le raffinement des places, le raffinement des transitions, le raffinement par sous-réseau et le raffinement de type. Nous avons dans notre travail proposé de nouvelles règles de raffinement de type et de transition. Nous essayons d'élargir le raffinement de type proposé par C. Lakos. Cet élargissement concerne la relation qui doit exister entre le type raffiné et le type abstrait et les modifications sur le type. En plus du principe de raffinement de C. Lakos, la relation de sous-typage définie par B. Liskov et J. Wing. La règle de raffinement de transition consiste à remplacer la transition abstraite par un sous-réseau qui comprend des transitions dites alternatives. Nous avons mené des études de cas pour illustrer ces règles de raffinement et développé un outil d'aide à la conception des modèles exprimés en réseaux de Petri colorés.

APA, Harvard, Vancouver, ISO, and other styles

9

Feuillade, Guillaume. "Spécification logique de réseaux de Petri." Rennes 1, 2005. http://www.theses.fr/2005REN1S168.

Full text

Abstract:

Cette thèse porte sur la spécification logique de systèmes concurrents et la synthèse d'un modèle : les systèmes sont les réseaux de Petri non étiquetés et les spécifications sont des formules temporelles. Par l'introduction des réseaux de compteurs et de formules de " test à zéro " d'un compteur, nous réduisons le problème indécidable de la vacuité du langage d'une machine à deux compteurs à celui de la synthèse de réseau à partir d'une formule du Mu-Calcul. Nous affaiblissons la logique en le Nu-Calcul Conjonctif (NCC), et nous lui associons un reconnaisseur, les spécifications modales ; nous en exhibons une sous-classe pour laquelle la synthèse est décidable. Nous introduisons la théorie structurelle d'un réseau donné, exprimable en NCC, dont les modèles sont tous les réseaux qui contiennent le premier. Grâce à cette théorie, nous établissons l'indécidabilité de la synthèse pour le NCC par réduction du problème de l'exécution bornée d'une machine à compteurs.

APA, Harvard, Vancouver, ISO, and other styles

10

Grivet, Sébastien. "Dépliages efficaces de réseaux de Petri." Bordeaux 1, 2004. http://www.theses.fr/2004BOR12915.

Full text

Abstract:

Nous nous intéressons à la vérification de systèmes concurrents tels que les automates communicants et les réseaux de Petri. La vérification de tels systèmes est difficile parce que la présence des composants concurrents augmente de façon importante le nombre des états globaux. Divers techniques ont été proposées pour combattre ce phénomène d'explosion combinatoire. Dans cette thèse, nous nous concentrons sur la technique de dépliage de réseau de Petri. Cette technique tire parti de l'indépendance des actions pour donner une représentation concise des états d'un réseau de Petri. De nombreux travaux ont été réalisés dans ce domaine, mais les aspects d'implémentation ont été souvent négligés. A partir d'une étude expérimentale, nous mettons en avant les parties critiques d'un algorithme de dépliage. Nous proposons de nouvelles stratégies pour diminuer le temps et ccupation-mémoire du calcul. Certaines sont basées sur des techniques de cache et d'autres réduisent le nombre d'appels aux fonctions critiques. Nous introduisons ensuite un nouveau modèle: le produit de réseaux de Petri symétriques. Il nous permet d'effectuer le dépliage de façon modulaire. Nous l'appliquons au produit d'automates. Et les symétries nous permettent d'utiliser des files non bornées. Ces travaux aboutissent à la réalisation d'un outil, l'outil KissPN.

APA, Harvard, Vancouver, ISO, and other styles

11

Chehaibar, Ghassan. "Méthodes d'analyse hiérarchique des réseaux de Petri." Phd thesis, Ecole Nationale des Ponts et Chaussées, 1991. http://tel.archives-ouvertes.fr/tel-00519683.

Full text

Abstract:

L'objet de cette thèse est de définir des méthodes d'analyse hiérarchique des réseaux de Petri (un formalisme de modélisation du contrôle des systèmes distribués). Premièrement, nous étudions la transformation de réseaux par remplacement de sous-réseaux ouverts: une notion d'équivalence est définie telle que si on remplace un sous-réseau ouvert par un réseau équivalent on obtient un réseau équivalent au réseau d'origine; puis nous définissons la classe des réseaux réentrants, pour laquelle la vérification de l'équivalence, complexe en général, devient simple. Deuxièmement, l'examen de la composition de réseaux par fusion de places conduit à deux résultats: la conservation d'espace d'accueil dans certaines conditions d'indépendance par rapport aux places partagées, et celle de l'absence d'interblocage lors de la composition des réseaux à ressources ordonnées (dans un sens différent de la solution classique). Enfin, un nouveau concept de norme pour la preuve de la propriété d'espace d'accueil est défini, muni d'opérations de composition permettant une vérification modulaire de cette propriété.

APA, Harvard, Vancouver, ISO, and other styles

12

Hameurlain, Nabil. "L'héritage comportemental dans les réseaux de Petri." Toulouse 1, 1998. http://www.theses.fr/1998TOU10027.

Full text

Abstract:

L'héritage est l'un des principaux concepts de l'approche objet, à la fois comme un outil cognitif permettant de comprendre des systèmes complexes et comme une technique pour la réutilisation et l'extension du logiciel. Avec l'émergence de formalismes intégrant l'approche orienté objet et la théorie des réseaux de Petri, se pose la question de savoir comment l'héritage pourrait être supporté par de tels formalismes, pour leur permettre de bénéficier de ses avantages. L'héritage a été principalement défini dans les cadres des langages à objets séquentiels, et il s'avère que son extension aux langages concurrents soulève des problèmes théoriques difficiles. En effet, l'héritage ne doit plus prendre en compte seulement l'interface des composants d'un système, mais aussi leur comportement. L'objet de cette thèse est de proposer une définition de l'héritage adaptée aux réseaux de Petri (RP), et d'étudier dans quelle mesure elle favorise l'analyse incrémentale des systèmes modélises par réseaux de Petri. En fait, au lieu de donner la définition d'une seule relation d'héritage entre réseaux, nous énonçons les conditions que doit satisfaire toute relation d'héritage. En effet, il ne saurait être question de considérer une unique relation d'héritage entre RP, car l'héritage fait intervenir d'une part le mode de composition entre réseaux et d'autre part, le degré de finesse auquel on se situe pour caractériser le comportement d'un réseau ou d'un système. Schématiquement, nous considérons qu'une relation d'héritage est définie par un mode de composition cp entre réseaux et par une relation de preordre @sem, ou sem est une sémantique, caractérisant le comportement des réseaux, de telle sorte que n2 hérite de n1 ssi pour tout n, cp(n, n2) @sem cp (n, n1) ; de plus, nous demandons qu'une relation d'héritage ainsi définie satisfasse certaines propriétés, en terme de congruence et de préservation du comportement. En appliquant cette définition à divers modes de composition des RP et à diverses caractérisations de leur comportement, nous aboutissons aux conclusions suivantes : 1. La composition des RP par fusion de transitions est propice à la définition de "bonnes" relations d'héritage. 2. Si la caractérisation du comportement des réseaux repose sur un étiquetage de leurs transitions (qui détermine les actions observables). […]
Inheritance is an essential concept of the object-oriented (0-0) approach as it is both a cognitive tool to ease the understanding of complex systems and a technical support for software reuse and change. With the emergence of formalisms integrating the 0-0 approach and the Petri net (PN) theory, the question arises how inheritance may be supported by such formalisms, in order that they benefit from the advantages of this concept. Inheritance has been originally introduced within the framework of data processing and sequential languages, while PN are mainly concerned with the behaviour of concurrent processes. Moreover, it has been pointed out that inheritance within concurrent 0-0 languages entails the occurrence of many difficult problems. Thus, one may think that integrating the inheritance concept within the PN theory also raises some difficulties. This thesis provides a general framework for behavioural inheritance relations in Petri nets, based upon the preorder and equivalence relations which are considered in the study of concurrent systems (e. G. The language, failure or bisimulation ones). Then, this framework is used to define inheritance relations in the class of client/server nets ; such nets communicate in an asynchronous way by channel places according to a request/reply protocol. By the way, the importance of a remarkable class of nets, the reliable nets, is highlighted

APA, Harvard, Vancouver, ISO, and other styles

13

Klai, Kais. "Réseaux de Petri : vérification symbolique et modulaire." Paris 6, 2003. http://www.theses.fr/2003PA066171.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Nguyen, Hoang-Thach. "Réseaux de Petri stochastiques à forme produit." Paris 7, 2012. http://www.theses.fr/2012PA077041.

Full text

Abstract:

L'objectif de cette thèse est de caractériser et d'analyser les réseaux de Pétri stochastiques ayant une distribution stationnaire à forme produit. La première contribution est la caractérisation d'une classe de réseaux de Pétri à forme produit. On introduit la classe des Π2-nets pour lesquels une distribution stationnaire à forme produit existe pour tous les taux de transition, Ensuite, on montre que l'intersection de la classe des Π2-nets et de la classe des réseaux de Pétri à choix libres est une classe classique des réseaux de files d'attente à forme produit : les réseaux de Jackson. La deuxième contribution consiste en deux méthodes effectives pour créer des Π2-nets. La première méthode consiste à générer un Π2-net à partir du réseau vide en utilisant un ensemble de règles de synthèse. La deuxième méthode revient à ajouter des contraintes à un réseau existant afin de le transformer en un Π2-net. La troisième contribution est une caractérisation de la classe des Π2-nets en terme de complexité. On montre que les problèmes d'accessiblité et de vivacité pour les Π2-nets 1-bornés sont PSPACE-complets. Cependant, le problème de couverture pour les Π2-nets généraux est EXPSPACE-complet. La dernière contribution est l'introduction de la sous-classe des Π3-nets, pour lesquels la constante de normalisation peut être calculée efficacement par la programmation dynamique
The aim of this thesis is to characterise and to analyse stochastic Pétri nets which have a product-form steady-state distribution. The first contribution is the characterisation of a class of product-form Petri nets. We introduce the class of Π 2-nets for which a product-form steady-state distribution exists for every choice of transition rates. Next, we show that intersecting this class and the class of free-choice nets yields a classical class of product-form queueing networks: the Jackson networks. The second contribution consists of two effective methods to construct arbitrary Π 2-nets. One can either generate a Π 2-net from the empty net using a finite set of synthesising rules, or to directly modify an existing net. The third contribution is a characterisation of the Π 2-nets in term of complexity. We show that the reachability and liveness problems are PS PAC E-complete for 1-bounded Π 2-nets and that the coverability problem is EXPSPACE-complete for general Π 2-nets. Finally, we introduce the subclass of Π3-nets whose normalising constant can be efficiently computed using dynamic programming

APA, Harvard, Vancouver, ISO, and other styles

15

Le, Bail Jean. "Sur les réseaux de Petri continus et hybrides." Grenoble INPG, 1992. http://www.theses.fr/1992INPG0163.

Full text

Abstract:

Les reseaux de petri sont frequemment utilises pour modeliser des systemes a evenements discrets. Cependant, leur efficacite est limitee lorsque l'on etudie des systemes mettant en jeu un grand nombre d'entites. Afin d'eviter l'explosion du nombre d'evenements a prendre en compte lors de la simulation de tels systemes, les reseaux de petri continus sont introduits. Dans un premier temps, nous construisons le modele reseau de petri continu asymptotique. Ce modele se caracterise par des simulations rapides ainsi que par des resultats realisant une bonne approximation du modele discret. De nombreux systemes de production comportent certaines parties qui, lors de la simulation, generent un grand nombre d'evenements et d'autres qui en engendrent moins. C'est le cas, par exemple, lorsque l'on modelise d'une part le flux des pieces dans un atelier de fabrication et d'autre part, l'etat operationnel des machines qui composent cet atelier. Les reseaux de petri hybrides permettent de prendre en compte chacun de ces deux aspects en faisant coexister une partie discrete et une partie continue. Nous presentons ensuite une application des reseaux de petri hybrides aux systemes de production par lots. Le modele que nous avons defini est bien adapte a ce type de systemes car il permet de gerer les entites circulant dans l'atelier soit piece a piece, soit regroupees en lots de fabrication. Dans chacun de ces deux cas, le modele propose garantit des simulations rapides ainsi que des resultats precis

APA, Harvard, Vancouver, ISO, and other styles

16

Hujsa, Thomas. "Contribution à l'étude des réseaux de Petri généralisés." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066342/document.

Full text

Abstract:

De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels
Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems

APA, Harvard, Vancouver, ISO, and other styles

17

Alla, Hassane Lotfi. "Réseaux de Pétri colorés et réseaux de Pétri continus : application à l'étude des systèmes à évènements discrets." Grenoble INPG, 1987. http://www.theses.fr/1987INPG0057.

Full text

Abstract:

Presentation de mehodes et d'outils pour modelisation d'un systeme et pour sa validation. La validation formelle est effectuee par l'exploitation des invariants lineaires de marquages de places et de tris des transitions. Utilisation des reseaux de petri continus

APA, Harvard, Vancouver, ISO, and other styles

18

David, Nicolas. "Discrete Parameters in Petri Nets." Thesis, Nantes, 2017. http://www.theses.fr/2017NANT4108/document.

Full text

Abstract:

Afin de permettre une modélisation plus souple des systèmes, nous proposons d’étendre les réseaux de Petri par des paramètres discrets représentant le poids des arcs ou le nombre de jetons présents dans les places. Dans ce modèle, tout problème de décision peut être décliné sous deux versions, une universelle, demandant si la propriété considérée est vraie quelles que soient les valeurs que prennent les paramètres et une existentielle, qui s’interroge sur l’existence d’une valeur pour les paramètres telle que la propriété soit satisfaite. Concernant la couverture, nous montrons que ces deux problèmes sont indécidables dans le cas général. Nous introduisons donc des sous classes syntaxiques basées sur la restriction des paramètres aux places, aux arcs en sortie ou aux arcs en entrée des transitions. Dans ces différents cas, nous montrons que la couverture existentielle et universelle sont décidables et EXPSPACE-complètes. Nous étudions alors le problème de la synthèse de paramètres qui s’intéresse à calculer l’ensemble des valeurs de paramètres telles que la propriété considérée soit vraie. Sur les sous classes introduites, concernant la couverture, nous montrons que les ensembles solutions à la synthèse ont des structures fermée supérieurement (cas des arcs de sortie) et fermée inférieurement (cas des arcs d’entrée). Nous prouvons alors que ces ensembles se calculent par un algorithme de la littérature, proposé par Valk et Jantzen, dont les conditions d’application se réduisent aux problèmes de décision étudiés précédemment. Enfin nous étudions les frontières de décision en nous intéressant aux versions paramétrées de l’accessibilité pour ces sous classes
With the aim of increasing the modelling capability of Petri nets, we suggest that models involve parameters to represent the weights of arcs, or the number of tokens in places. We consider the property of coverability of markings. Two general questions arise, the universal and the existential one: “Is there a parameter value for which the property is satisfied?” and “Does the property hold for all possible values of the parameters”. We show that these issues are undecidable in the general case. Therefore, we also define subclasses of parameterised nets, depending on whether the parameters are used on places, input or output arcs of transitions. For some classes, we prove that universal and existential coverability become decidable, making these classes more usable in practice. To complete this study, we prove that those problems are EXPSPACE-complete. We also address a problem of parameter synthesis, that is computing the set of values for the parameters such that a given marking is coverable in the instantiated net. Restricting parameters to only input weights (preT-PPNs) provides a downward-closed structure to the solution set. We therefore invoke a result for the representation of upward closed set from Valk and Jantzen. The condition to use this procedure is equivalent to decide the universal coverability. We also propose an adaptation of this reasoning to the case of parameters used only as output weights (postT-PPNs). In this case, the condition to use this procedure can be reduced to the decidability of the existential coverability. Finally, we broaden this study by establishing decision frontiers through the study of existential and universal reachability

APA, Harvard, Vancouver, ISO, and other styles

19

Traonouez, Louis-Marie. "Vérification et dépliages de réseaux de Petri temporels paramétrés." Phd thesis, Université de Nantes, 2009. http://tel.archives-ouvertes.fr/tel-00466429.

Full text

Abstract:

Les travaux présentés portent sur l'étude de méthodes de vérification paramétrée des systèmes temps réels. La motivation pour ces recherches est de proposer des méthodes formelles à appliquer sur des systèmes dont les spécifications ne sont pas encore complètes. Des paramètres sont donc introduits dans les modèles utilisés afin de donner des degrés de liberté à la modélisation. Le but est alors de guider la conception du système en déterminant des valeurs satisfaisantes pour les paramètres.

Nous nous sommes focalisé sur les paramètres temporels qui sont en général parmi les plus complexes à définir. Nous avons ainsi défini le modèle des réseaux de Petri à chronomètres paramétrés.

Dans une première approche, nous étendons les méthodes d'analyse classiquement utilisées dans les réseaux de Petri temporels. L'espace d'états du modèle paramétré est ainsi représenté par le graphe des classes d'états paramétrées. Cela nous permet de proposer des semi-algorithmes de model-checking paramétré avec lesquels nous vérifions des formules de logique TCTL paramétrées.

Dans une seconde approche, nous étudions les méthodes qui préservent le parallélisme des réseaux de Petri. L'intérêt est de limiter l'explosion combinatoire qui apparaît lors de l'analyse de systèmes distribués, en particulier avec des modèles paramétrés. Nous proposons pour cela une méthode de dépliage temporel paramétré. Ce dépliage est a priori infini, mais nous proposons de l'utiliser pour résoudre un problème de supervision. La construction du dépliage est alors guidée par des observations finies, et nous extrayons les explications de ces observations, ainsi que les contraintes sur les paramètres qu'elles induisent.

APA, Harvard, Vancouver, ISO, and other styles

20

Marteau, Stéphane. "Commande de systèmes temps réel par réseaux de Petri." Angers, 1997. http://www.theses.fr/1997ANGE0023.

Full text

Abstract:

Cette thèse s'inscrit dans le cadre de la mise en œuvre d'applications temps réel. Plus précisément, l'objectif est de définir une modélisation générale des systèmes temps réel permettant leur commande, basée sur les réseaux de Petri. La mise en œuvre d'applications temps réel impose de nombreuses contraintes. Les temps de réponse du système de contrôle doivent être adaptés pour maintenir le procédé dans un état sécuritaire. Ce critère d'urgence entre directement en jeu dans les politiques d'ordonnancement des tâches de l'application. Se pose alors le problème de la sûreté de fonctionnement dans le cas où les contraintes temporelles ne sont pas respectées. Le système de contrôle doit donc intégrer de façon autonome une certaine capacité de décision. Enfin, il doit prendre en compte les divers dispositifs d'entrées/sorties du procédé. Dans la première partie de ce manuscrit, nous présentons toutes les bases nécessaires à la compréhension des idées et solutions exprimées par la suite, en terme de généralités et concepts de base des systèmes temps réel et de formalismes issus des réseaux de Petri. La seconde partie propose tout d'abord une analyse de modèles de réseau de Petri généralisé et de haut niveau. Cette étude aboutit au résultat que la maîtrise d'un système temps réel requiert un autre type de modèle. Nous définissons alors ce que nous appelons les réseaux de Petri Fp. La structure de corps associée aux couleurs permet la définition de transitions algébriques, qui confèrent au modèle une puissance de décision. La détermination de fonctions polynomiales autorise des séquencements complexes d'évolution. Nous considérons alors la possibilité d'évaluer des polynômes de transformation afin de permettre aux applications de modifier dynamiquement certains de leurs paramètres. Enfin, nous proposons une commande des systèmes temps réel basée sur un système de contrôle constitué d'un modèle global en trois couches. Celui-ci permet alors de répartir les différentes contraintes qui existent sur le procédé. La Partie Commande prend en compte tous les dispositifs d'entrées/sorties. La Partie Décisionnelle a pour rôle la prise de décision. La Partie Temporelle contribue à l'expression et à la recherche de solutions pour le respect des contraintes temporelles, et supporte un module de sûreté de fonctionnement.

APA, Harvard, Vancouver, ISO, and other styles

21

Dardour, Amira. "Estimation et diagnostic de réseaux de Petri partiellement observables." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0054/document.

Full text

Abstract:

Avec l'évolution de la technologie, l'homme a procédé à la conception de systèmes de plus en plus complexes mais aussi de plus en plus sensibles aux défauts qui peuvent les affecter. Une procédure de diagnostic contribuant au bon déroulement du processus est ainsi nécessaire. Dans ce contexte, le but de cette thèse est le diagnostic des systèmes à événements discrets modélisés par des Réseaux de Petri Étiquetés (RdPE) partiellement observables. Sous l'hypothèse que chaque défaut est modélisé par le tir d'une transition non observable, deux approches de diagnostic à base d'estimation d'état sont développées. Une première approche composée de deux étapes consiste à estimer l'ensemble des marquages de base sur un horizon élémentaire glissant. La première étape consiste à déterminer un ensemble de vecteurs candidats à partir d'une approche algébrique. La deuxième étape consiste à éliminer les solutions candidates calculées qui ne sont pas associées à une trajectoire possible du RdPE. Comme l'ensemble des marquages de base pourra aussi être important, une deuxième approche de diagnostic évitera cet écueil en n'estimant pas les marquages. Une technique de relaxation des problèmes de Programmation Linéaire en Nombres Entiers (PLNE) sur un horizon fuyant est utilisée afin d'avoir un diagnostic en temps polynomial
With the evolution of technology, humans have made available systems increasingly complex but also increasingly sensitive to faults that may affect it. A diagnostic procedure which contributes to the smooth running of the process is thus necessary. In this context, the aim of this thesis is the diagnosis of discrete event systems modeled by partially observed Labeled Petri Nets (LPNs). Under the assumption that each defect is modeled by the firing of an unobservable transition, two diagnostic approaches based on state estimation are developed. A first approach is to estimate the set of basis markings on a sliding elementary horizon. This approach is carried out in two steps. The first step is to determine a set of candidate vectors from an algebraic approach. The second step is to eliminate the calculated candidate solutions that are not associated with a possible trajectory of the LPN. As the set of basis markings can also be huge, a second diagnostic approach will avoid this pitfall by not estimating the markings. A relaxation technique of Integer Linear Programming (ILP) problems on a receding horizon is used to have a diagnosis in polynomial time

APA, Harvard, Vancouver, ISO, and other styles

22

Collart-Dutilleul, Simon. "Réseaux de Petri P-temporels: Modélisation et validation d'exigences temporelles." Habilitation à diriger des recherches, Université des Sciences et Technologie de Lille - Lille I, 2008. http://tel.archives-ouvertes.fr/tel-00364666.

Full text

Abstract:

Le corps de ce travail concerne la modélisation des systèmes à événements discrets. Il s'intéresse par ailleurs en quasi exclusivité à la gestion des contraintes de temps de séjour. Mes travaux de thèse ont comporté la constitution du cahier des charges en amont et les applications en aval d'un outil de modélisation des exigences temporelles : Les Réseaux de Petri P-temporels. L'ensemble de mes travaux de recherche a été développé dans le but d'asseoir l'utilisation de cet outil. Un premier axe a été de positionner l'outil par rapport à ceux de l'état de l'art. Une deuxième tâche a été de prouver un certains nombre de propriétés mathématiques dans l'optique de permettre des applications industrielles efficaces. Au delà de la stricte recherche de propriété, l'extension du champ applicatif, vers le domaine du ferroviaire par exemple, a pris une part très importante. Une troisième activité a débouché sur la caractérisation des limites du modèle et la proposition d'extension fonctionnelle ou de rapprochement de l'outil de modélisation vers des modèles existants. Ce modèle concerne donc les Systèmes à Evénements Discrets où l'on rencontre des contraintes de temps de séjour maximum dans un état donné. C'est le cas de la galvanoplastie qui a été le premier support applicatif. Très rapidement, le champ des applications potentielles de l'outil a été élargi par des publications dans les domaines de l'industrie alimentaire. Les travaux se sont par ailleurs concentrés sur la partie commande, en supposant que la séquence des opérations avait déjà été fixée. Ils ont été appuyés par le travail de master de recherche de M.F. Karoui en 2004 (deux conférences ont été publiées dans la suite de son mémoire). Par ailleurs, l'expertise en supervision qui se trouvait au sein de l'équipe Système à Evénement Discret a été valorisée par le stage de master de T. Lecuru sur la supervision des ateliers automobiles en 2003. Ce travail a pris une autre ampleur avec la thèse de Jerbi Nabil sur la commande des ateliers à contraintes de temps soutenue en 2006 (3 publications de revue). Il se poursuit avec la thèse de Annis Mhalla. En 2006, F. Defossez soutient un master dans le domaine ferroviaire sur la gestion des exigences temporelles de sécurité. Ce dernier va s'inscrire en troisième année de thèse et a déjà publié 5 conférences. Ce travail ouvre un champ très important pour l'outil de modélisation que je porte. Par exmple, cela a amné la participation à un projet Européen. Ce projet SELCAT qui s'intéresse au passage à niveau et qui s'est terminé en juin 2008. Il se prolongera dans un projet national ANR accepté qui débutera autour de janvier 2009. En parallèle, un projet spécifique ayant trait aux outils de modélisation sur les chantiers est en cours avec la SNCF. Enfin, la thèse de Hedi Dhouibi a été l'occasion de proposer un nouveau modèle capable de généraliser certaines propriétés des Réseaux de Pétri P-temporels à des systèmes où le paramètre critique est différent du temps. Une validation industrielle sur des données réelles a pu être effectuée (soutenance en 2005). Elle fait l'objet de trois publications de revues internationales (acceptation en 2008).

APA, Harvard, Vancouver, ISO, and other styles

23

Gallon, Laurent. "Le modèle réseaux de Petri temporisés stochastiques: extensions et applications." Phd thesis, Université Paul Sabatier - Toulouse III, 1997. http://tel.archives-ouvertes.fr/tel-00132834.

Full text

Abstract:

Cette thèse s'inscrit dans le cadre général de l'utilisation des techniques formelles lors de la phase conceptuelle des systèmes distribués temps-réel, et concerne plus précisément l'extension des pouvoirs d'expression et d'analyse du modèle Réseaux de Petri Temporisés Stochastiques. Ce modèle, qui appartient à la classe des Réseaux de Petri Stochastiques, associe à chaque transition un intervalle de temps, et une distribution de probabilité sur cet intervalle (ceci permet de représenter des caractéristiques temporelles variées et en particulier des contraintes) En ce qui concerne le pouvoir d'expression, nous avons introduit, d'une part, la notion de mémoire temporelle de toutes les sensibilisations (ceci est important pour l'étude des phénomènes de préemption que l'on rencontre dans des algorithmes d'ordonnancement et dans des problèmes de sûreté de fonctionnement) et, d'autre part, plusieurs règles de tir de transitions (en particulier les règles MIN et MAX qui permettent des études des cas pires, aspect important dans les systèmes temps-réels). Les graphes ainsi obtenus ont été également situés par rapport à la référence comportementale que constitue le graphe des classes d'états (obtenu à partir des Réseaux de Petri Temporels). En ce qui concerne le pouvoir d'analyse, nous avons défini le concept d'automate quotient quantifié (concept basé, à la fois, sur la relation d'équivalence de Milner et les règles de réduction de Beizer), qui a deux qualités importantes : il permet, d'une part, d'obtenir des modèles, à la fois qualitatifs et quantitatifs de services de communication ; et, d'autre part, de contrôler les dimensions des modèles à traiter lors de la modélisation d'architectures de communication multicouches. Ce modèle a été appliqué à un exemple industriel, le protocole embarqué temps-réel ARINC 629 CP. L'étude faite a mis en évidence les propriétés temps-réel et de tolérance aux pannes de ce protocole.

APA, Harvard, Vancouver, ISO, and other styles

24

GIRAULT, François. "Formalisation en logique linéaire du fonctionnement des réseaux de Petri." Phd thesis, Université Paul Sabatier - Toulouse III, 1997. http://tel.archives-ouvertes.fr/tel-00010245.

Full text

Abstract:

En logique classique, la formalisation du fonctionnement des réseaux de Petri (RdP) se heurte à la pérennité de la vérité. En logique modale, elle impose la construction préalable du graphe des marquages accessibles. A contrario, la logique linéaire (LL) fondée par Girard permet de formaliser directement par des séquents prouvables purement propositionnels les relations d'accessibilité dans les RdP : toute transition apparaît comme une implication linéaire disponible ad libitum entre les propositions traduisant ses marquages d'entrée et de sortie. Pour approfondir cette formalisation, nous définissons comme primitives en LL les notions de ressource, d'action et de consommabilité/productibilité, analogues mais distinctes de celles de proposition, de déduction et de vérité/fausseté en logique classique. Nous développons une interprétation concrète pour tous les connecteurs linéaires en cohérence avec leurs propriétés syntaxiques. Nous présentons le connecteur « par » comme un opérateur de cumul disjoint d'exemplaires de ressources (dual du connecteur « fois » de cumul conjoint) et la négation linéaire « nil » comme un inverseur du sens du temps. Cette concrétisation montre les limites des formalisations existantes des RdP en LL ; nous les généralisons en traduisant chaque transition par une implication linéaire ordinaire, traitée comme une ressource périssable, dont tout exemplaire consommé correspond à une occurrence de franchissement. Ainsi, nous apportons une expression logique aux aspects primordiaux du fonctionnement des RdP : nous démontrons qu'une relation d'accessibilité par séquence de transitions équivaut à un séquent prouvable et que l'équation fondamentale est l'expression algébrique d'un corollaire du critère d'équilibrage en LL. Grâce à la combinatoire de tous les connecteurs linéaires, notre approche ouvre des perspectives d'analyse de relations complexes d'accessibilité comme celles de reprise après défa illance dans un système industriel.

APA, Harvard, Vancouver, ISO, and other styles

25

Rezig, Sadok. "Approches canoniques pour la synthèse des contrôleurs réseaux de Petri." Thesis, Université de Lorraine, 2016. http://www.theses.fr/2016LORR0117/document.

Full text

Abstract:

Dans ce mémoire, nous présentons différentes approches de synthèse de contrôleurs réseaux de Petri en se basant sur la théorie des régions. Cette théorie présente quelques limites dans la synthèse de contrôle. En effet, la synthèse du contrôleur RdP, s’il existe, n’est pas du tout une tâche facile vue sa complexité de calcul et l’explosion combinatoire des états dans le graphe de marquage. De plus, le système linéaire de la théorie des régions à résoudre peut contenir des combinaisons convexes entre ces équations ce qui rend la théorie insoluble pour calculer les superviseurs RdP. Ce travail vise à simplifier la complexité de calcul de la théorie des régions en réduisant le nombre d’équations du système linéaire de la théorie des régions d’une part, et d’autre part en minimisant le temps de calcul des contrôleurs RdP. De nouveaux concepts de coupes minimales et de marquages canoniques ont été introduits afin d’appliquer la théorie des régions sur des zones précises du graphe et non pas sur la totalité du graphe de marquage. Finalement, deux autres nouvelles approches ont été développées pour synthétiser des contrôleurs RdP sans générer le graphe de marquage
In this work, we present different control synthesis approaches based on Petri nets and the theory of regions. This theory has some limitations in supervisory control. Indeed, the design on the PN controller, if it exists, is not an easy task due to the resolution complexity and the combinatorial explosion of states in the generated reachability graph. In addition, the linear system of the theory of regions may contain convex combinations of its equations making the theory insoluble. This work aims to simplify the computational complexity of the theory of regions by reducing the number of equations of the linear system and decreasing the computation time of PN controllers. Consequently, new concepts of minimal cuts and canonic markings are introduced in order to apply the theory of regions on specific zones of the graph and not on the whole reachability graph. Finally, two new approaches are developed to synthesize PN controllers without generating the reachability graph

APA, Harvard, Vancouver, ISO, and other styles

26

Berghoute, Bekrar Rebiha. "Identification des systèmes à événements discrets par réseaux de Petri." Reims, 2009. http://theses.univ-reims.fr/exl-doc/GED00001123.pdf.

Full text

Abstract:

Dans ce travail, nous proposons deux méthodes originales d'identification d'une classe de systèmes à événements discrets (SED) modélisables par réseaux de Petri (RdP). La première méthode consiste à utiliser les signaux de sortie du système afin d'élaborer son modèle comportemental sous la forme d'un RdP. Les conditions nécessaires et suffisantes pour garantir l'unicité de la solution sont établies. Par ailleurs, le problème d'identification d'un SED est défini sous la forme d'un problème de programmation linéaire binaire. Quant à la deuxième méthode, elle est basée sur l'analyse des signaux d'entrée et de sortie mesurables du système considéré. Elle consiste à déterminer la partie mesurable et à estimer la partie non mesurable puis, à calculer la structure et le marquage initial du RdP à identifier. Par ailleurs, deux approches de synthèse de contrôleur RdP sont proposées. Ces derniers permettent de raffiner les modèles issus de la première phase en inhibant, quand c’est nécessaire, l’atteignabilité des états interdit. Les résultats obtenus dans ce travail ont été validés sur un système réel
In this thesis we have proposed two original identification approaches of a class of discrete event systems using Petri Nets. Our first proposed approach consists in using the output symbols of the target system to elaborate its behavioural model in PN form. The necessary and the sufficient conditions for the existence of a unique solution are established. Moreover, the identification problem is defined as a binary linear programming problem where the uniqueness of the solution is not guarantee. For our second method, it based on using the measurable input and output system signals. It consists in calculating the measurable part, estimating the non measurable one and developing different algorithms to estimate the structure and the initial marking of a PN model to be identified. However, the latter can generate, in some times, some behaviours which are not equivalent to those generated by the real system. These behaviours are considered as illegal. To inhibit the identified model to access to these illegal states two synthesis approaches of PN controller are proposed. Finally, the results obtained in this thesis have been validated on a real system

APA, Harvard, Vancouver, ISO, and other styles

27

Magnin, Morgan. "Réseaux de Petri à chronomètres : temps dense et temps discret." Nantes, 2007. http://archive.bu.univ-nantes.fr/pollux/show.action?id=006a7b1c-26bd-451f-a65a-1ee889ff0f4c.

Full text

Abstract:

Dans cette thèse, nous comparons les approches en temps dense et en temps discret pour la vérification de systèmes temps réel via une extension des réseaux de Petri temporels, appelée réseaux de Petri à chronomètres. Le temps dense consiste à considérer le temps comme une grandeur dense tandis que le temps discret l'assimile à une grandeur discrète. Les applications physiques évoluent par rapport au temps physique qui est continu ; toutefois, l'évolution du procédé n'est en général observée par le système informatique qui le pilote qu'à des instants particuliers (échantillonnage ou observations sporadiques). De plus, le système de pilotage est composé de tâches qui sont exécutées sur un (ou plusieurs) processeur(s) dont le temps physique est discret. Le recours à un temps dense lors de la modélisation conduit donc à une surapproximation du système informatique. Mais l'intérêt majeur du temps dense réside dans les abstractions symboliques associées, pratiques à mettre en oeuvre et contenant l'explosion combinatoire des états. Nous avons commencé par améliorer les méthodes de calcul de l'espace d'états en temps dense. Nous avons ensuite établi une classification des réseaux de Petri en temps discret. Nous avons proposé une méthode efficace de calcul énumératif de l'espace d'états de modèles en temps discret. Comme toute méthode purement énumérative, celle-ci souffre toutefois de l'explosion combinatoire du nombre d'états. C'est pourquoi nous avons conçu une méthode symbolique permettant de calculer l'espace d'états d'un modèle en temps discret en adaptant les techniques habituellement réservées au temps dense
In this thesis, we compare the dense-time and discrete-time approaches for the verification real time systems modelled with an extension of time Petri nets, namely stopwatch Petri nets. In dense-time semantics, time is considered as a dense quantity while, in discrete-time semantics, it is considered as a discrete variable. The physical systems (the processes) follow a dense-time evolution. The observation of the process is however usually performed through an IT command system which pilots it only at some peculiar instants (digitalization or periodic observations). In addition, the command system is composed of tasks that are executed on one (or many) processor(s) for which physical time is discrete. Dense-time thus leads to an over-approximation of the IT system. The major advantage of dense-time lies in the symbolic abstractions it offers: they are easy to put into application and they avoid the combinatorial explosion of states. First we improved the dense-time state space computation of stopwatch Petri nets. We then established a complete classification of discrete-time models in terms of expressivity and decidability results. We proposed an efficient enumerative procedure for computing the state space of discrete-time nets. As every enumerative method, it however suffers from the combinatorial explosion of the number of states. That is why we finally focused on a symbolic method for computing the state space of discrete-time models by extending to discrete-time semantics the techniques usually applied for dense-time models

APA, Harvard, Vancouver, ISO, and other styles

28

Bousseau, Frédéric. "Modélisation des systèmes complexes : une approche par réseaux de Petri." Angers, 1997. http://www.theses.fr/1997ANGE0008.

Full text

Abstract:

L’étude des divers systèmes de notre monde est souvent faite par l’intermédiaire d'un modèle. Celui-ci n'est qu'une représentation de la réalité qui ne peut pas être complètement exacte. Cette erreur de modélisation est due, entre autres, à l'environnement du système dont on ne peut pas toujours tenir compte. En effet, tout système est une sous partie d'un autre, plus grand, et peut être, lui-même, décomposé en nombreux sous-systèmes. Cette thèse propose une étude des systèmes interconnectés. Nous allons modéliser et analyser des systèmes qui présentent de nombreuses interactions. Les automates cellulaires sont parmi les plus célèbres modèles de ces systèmes que l'on appelle complexes. L’originalité de ce travail est de proposer l'utilisation des réseaux de Petri comme outil de modélisation de ces systèmes Ces réseaux présentent deux aspects très intéressants : la simplicité de la modélisation et un support algébrique associé qui permet une analyse mathématique du modèle Nous proposons dans cette thèse une méthode de modélisation des systèmes complexes. Celle-ci est basée sur l'utilisation d'un réseau de Petri de base que nous appelons une cellule. Nous lions ensuite ces cellules entre elles afin d'obtenir notre modèle. Nous analysons le comportement de ces modèles en termes d'attracteurs en utilisant le support mathématique associé aux réseaux de Petri et notamment les invariants. Nous étudions enfin les effets des perturbations sur nos modèles. Pour terminer, nous présentons quelques perspectives d'applications liées à notre étude Ces applications sont principalement dédiées aux systèmes ayant une évolution cyclique.

APA, Harvard, Vancouver, ISO, and other styles

29

Bonhomme, Patrice. "Réseaux de Petri P-temporels : contributions à la commande robuste." Chambéry, 2001. http://www.theses.fr/2001CHAMS012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Fraisse, Pierre. "Cycles et facteurs dans les graphes : application de la théorie des graphes aux réseaux de Pétri." Paris 11, 1985. http://www.theses.fr/1985PA112100.

Full text

Abstract:

Cette thèse se compose de plusieurs chapitres/ le premier porte sur l’existence de certains cycles dans des graphes de grand degré. Il donne des résultats de conditions suffisantes d’existence du cycle de longueur supérieure à un nombre m fixé, de cycle dominant, de circuit contenant s sommets et de longueur au plus 2s. Le second porte sur des conditions suffisantes d’existence de f-facteurs de graphes, avec condition de stabilité et connexité, d’une part, nombre d’arcs, d’autre part, existence de f-facteurs dans certains sous-graphes, enfin. Le troisième porte sur les couvertures des arêtes et des sommets d’un graphe par une famille de cycles de longueur totale minimale. Enfin le quatrième traite d’une application de la théorie des graphes à la théorie des réseaux de Petri. Il donne des conditions suffisantes de vivacité pour certains réseaux
This thesis is constituted by several chapters. The first one deals with the existence of certain cycles in graphs of large degree. It gives sufficient conditions for the existence of cycles of length greater than a given number m, of dominating cycles, of circuits containing a set of s vertices and of length at most 2s. The second one gives sufficient conditions for the existence of f-factors in graphs, with conditions of independence number and connectivity, of number of edges, and also by assuming the existence of f-factors in some subgraphs. The third deals with covering of edges and vertices of a graph by cycles, the sum of the length of the cycles being minimal. Finally, the fourth is an application of the graph theory to Petri nets. It gives sufficient conditions for liveness on a class of nets

APA, Harvard, Vancouver, ISO, and other styles

31

Dedova, Anna. "Specification and Verification of the NEO Storage Distributed Protocol." Paris 13, 2012. http://www.theses.fr/2012PA132004.

Full text

Abstract:

Le protocole NEO a été développé pour la gestion d’une base de données distribuée à grande échelle. Il est executé sur un ensemble de machines (nœuds) qui constituent un cluster de machines. Ce dernier contient plusieurs types de nœuds : des nœuds de stockage qui servent à stocker la base de données, plusieurs nœuds maîtres qui vont élire l’un d’eux (maître primaire) ayant la tâche de contrôler l’ensemble du cluster, et enﬁn les nœuds clients servant à l’envoi et à la réception des différentes requêtes. Dans le cadre des travaux de thèse, un modèle de réseaux de Petri coloré est proposé pour le protocole NEO. Ce modèle a été élaboré dans le but de spéciﬁer et vériﬁer des propriétés attendues du protocole. Les phases d’élection du maître primaire ainsi que de démarrage ont été modélisées et vériﬁées avec succès dans plusieurs conﬁgurations de base des données et du cluster. Les proprietés importantes de protocole ont été formalisées et veriﬁées automatiquement sûr plus d’une centaine des conﬁgurations initiales. Les résultats négatifs ont été soumis à l’analyse inverse. Dans le même temps, une nouvelle methodologie de modélisation été proposée. La méthode comprend plusieurs étapes présis à suivre pour obtenir un réseau de Petri coloré à partir du code source de haut niveau orienté objet
The NEO protocol was developed to manage a large scale distributed data base. It is executed on a set of machines (nodes) that form a cluster. The cluster consists of nodes of different types: storage nodes, which store the database, several master nodes, which choose one among them (the primary master) that will control the whole cluster, and, ﬁnally, client nodes which send and receive different requests from users. As part of the thesis work, a coloured Petri net model was proposed for the NEO protocol. This model was constructed for the purpose of speciﬁcation and veriﬁcation of the expected properties of the protocol. The phases of the election of the primary master as well as the bootstrap phase was modelled and successfully veriﬁed on various cluster and database conﬁgurations. The important properties of the protocol were found, formalised and automatically veriﬁed on more than a hundred initial conﬁgurations. The negative results were subjected to backward analysis. At the same time, a new modelling methodology was proposed. The method consists of precise steps to follow in order to get a coloured Petri net model from high level object oriented source code, thus achieving retro-engineering

APA, Harvard, Vancouver, ISO, and other styles

32

Stöcker, Jan. "Un modèle intermédiaire pour la vérification des systèmes asynchrones embarqués en temps réel : définition et application du langage ATLANTIF." Grenoble INPG, 2009. http://www.theses.fr/2009INPG0084.

Full text

Abstract:

La validation des systèmes critiques réalistes nécessite d'être capable de modéliser et de vérifier formellement des données complexes, du parallélisme asynchrone, et du temps-réel simultanément. Des langages de haut-niveau ont une syntaxe concise et une grande expressivité pour représenter ces aspects. Cependant, ils disposent de peu d'outils logiciels permettant d'appliquer des algorithmes efficaces du model-checking. Néanmoins, de tels outils existent pour des modèles graphiques, de niveau plus bas, tels que les automates temporisés et les réseaux de Petri temporisés. Les modèles intermédiaires sont un moyen pour combler le fossé qui sépare les langages des modèles graphiques. Dans cette thèse, nous proposons un nouveau modèle nommé ATLANTIF, qui enrichit le modèle NTIF de constructions temps-réel et de compositions parallèles de processus séquentiels. Leur synchronisation est exprimée d'une manière simple et intuitive par la nouvelle notion de synchroniseur. Nous montrons qu'ATLANTIF est capable d'exprimer les constructions principales des langages de haut-niveau. Nous présentons aussi des traducteurs d'ATLANTIF vers des modèles graphiques. Ainsi, ATLANTIF étend la classe des systèmes qui peuvent en pratique être vérifiés formellement, ce que nous illustrons par un exemple
The validation of real-life critical systems raises the challenge of being able to formally model and verify complex data, synchronous concurrency, and real-time aspects simultaneously. High-Ievellanguages, such as those inheriting from the theoretical foundations of process algebras, provide a concise syntax and a high expressive power regarding these aspects. Yet, they lack software tools enabling the application of efficient model checking algorithms. On the other hand, such tools exist for graphical, lower level, models such as timed automata (e. G. , UPPAAL) and time Petri nets (e. G. , TINA). Intermediate models are a key to bridge the gap between languages and graphical models. For instance, NTIF (New Technology Intermediate Format) was proposed to represent untimed sequential processes that handle complex data. Ln this thesis, we propose a new model named ATLANTIF, which extends NTIF with real-time constructs and parallel compositions of sequential processes. Their synchronization is expressed in a simple and intuitive way using the new notion of synchronizers. We show that ATLANTIF is capable of expressing the main constructs of high-Ievellanguages. We also present translators from ATLANTIF to timed automata (for verification using UPPAAL) and to time Petri nets (for verification using TINA). Thus, ATLANTIF extends the class of systems that can practically be formally verified, which we iIIustrate along an example

APA, Harvard, Vancouver, ISO, and other styles

33

Hennequin, Sophie. "Multi-modèle flou pour la commande des systèmes de production." Besançon, 2000. http://www.theses.fr/2000BESA2020.

Full text

Abstract:

Ce travail concerne la modélisation et la commande des systèmes de production. Des multi-modèles flous de type Takagi-Sugeno-Kang sont définis pour représenter le travail des machines. Ces modèles s'inspirent des réseaux de Petri dépendant du temps, et en particulier des réseaux de Petri T-temporisés sans conflit ou continus à vitesses variables. Le comportement de chaque transition est décrit à l'aide de deux règles floues qui correspond à une linéarisation locale et permet d'appliquer simplement une commande analytique. L'objectif de cette commande est de faire suivre à un ou plusieurs stocks une valeur désirée. Des commandes continues, discrètes et hybrides sont étudiées. Pour l'approche continue, la convergence du modèle global commandé est démontrée sous réserve que les modèles locaux convergent. Pour l'approche discrète, une commande tout ou rien est proposée qui minimise l'erreur quadratique entre la consigne et la valeur réelle du stock.

APA, Harvard, Vancouver, ISO, and other styles

34

Huvenoit, Bertrand. "De la conception à l'implantation de la commande modulaire et hiérarchisée de systèmes flexibles de production manufacturière." Lille 1, 1994. http://www.theses.fr/1994LIL10134.

Full text

Abstract:

Nous presentons dans ce memoire une methodologie de conception et d'implantation de la commande d'un systeme flexible de production manufacturiere. Dans notre demarche de conception, nous utilisons le formalisme des reseaux de petri et le formalisme objets. A l'issue de cette phase de conception basee sur une capitalisation de l'experience acquise sous forme de bibliotheques de composants de base reutilisables, nous obtenons un modele de commande ouvert a la fois modulaire et hierarchise ou les aspects decisionnels sont bien dissocies. Dans notre demarche d'implantation, nous exploitons directement la genericite et la modularite degagees en conception grace a l'utilisation du langage ada. Nous proposons une methode et une structure d'implantation qui permettent d'obtenir un ensemble d'objets a faible couplage. L'integration de ces derniers et de quelques objets annexes permet d'obtenir, d'une part, un logiciel de simulation de la commande en mesure de valider le comportement dynamique de celle-ci et d'autre part, le logiciel d'exploitation pouvant etre implante, suivant plusieurs configurations, sur l'architecture informatique repartie du site de production.

APA, Harvard, Vancouver, ISO, and other styles

35

Hillion, Hervé P. "Modélisation et analyse des systèmes de production discrets par les réseaux de Petri temporisés." Paris 6, 1989. http://www.theses.fr/1989PA066243.

Full text

Abstract:

Nous présentons, dans ce travail, une approche basée sur les réseaux de Petri temporisés (déterministes) pour la modélisation et l'analyse des systèmes de production discrets. L'étude porte d'une part sur les job-shops (ateliers flexibles), d'autre part sur les systèmes d'assemblage multi-niveaux. Le processus de production fonctionne de manière cyclique (il s'agit de fabrications répétitives) avec un nombre limité d'en-cours et pour des ratios de productions fixés. A partir du modèle développé pour les job-shops, qui correspond à un graphe d'évènements temporisé, nous en déduisons les caractèristiques du régime permanent et en particulier les performances (productivité, utilisation des machines. . . ) en fonction de l'état initial et de l'ordre de passage des pièces sur les machines (séquences d'entrée). Nous examinons ensuite comment optimiser les performances en saturant la machine la plus chargée avec un minumum d'en-cours. Cet aspect est particulièrement important dans le cas des ateliers flexibles car cela revient à maximiser la productivité avec le minimum de ressources de transport. Nous montrons que cette condition est toujours réalisable pour un job-shop (quelles que soient les séquences d'entrée dans les machines) et nous proposons des algorithmes heuristiques de recherche d'un ordonnancement optimal. Dans le cas d'un système d'assemblage multi-niveaux, le modèle s'appuie sur les réseaux de Petri généralisés. L'étude des propriétés de fonctionnement périodique de ces réseaux permet de calculer les performances maximales du système de production en fonction du niveau des en-cours (qui représentent dans ce cas les matières premières et les produits semi-finis). Nous abordons également le problème d'optimisation des performances en suivant une démarche similaire à celle des job-shops.

APA, Harvard, Vancouver, ISO, and other styles

36

Bertrand, Olivier. "Détection d'activités par un système de reconnaissance de chroniques et application au cas des simulations distribuées HLA." Paris 13, 2009. http://www.theses.fr/2009PA132039.

Full text

Abstract:

L’objectif est de fournir un moyen simple pour analyser des simulations distribuées de type HLA (High Level Architecture). Pour cela nous avons choisi la reconnaissance de chroniques, et nous décrivons les activités recherchées par des chroniques (avec CRS/Onera). Nous effectuons tout d’abord une modélisation formelle du système de reconnaissance de chroniques utilisé (CRS/Onera). Pour cela nous avons tout d’abord comparé l’expressivité de différents modèles à base d’automates. Nous avons retenu les réseaux de Petri colorés qui nous ont permis d’avoir un modèle élégant et modulaire. Nous avons prouvé pour certaines constructions, le bon fonctionnement des réseaux de Petri construits. Puis nous avons modélisé un système de gestion d’événements en réseaux de Petri colorés. Avec ce modèle, nous validons le comportement de l’outil de reconnaissance par exemple pour les expressions de chroniques interdites et les chroniques avec répétition d’événements. Pour détecter des activités, nous intégrons CRS/Onera dans un composant standard (un fédéré) d’une simulation HLA. Pour réaliser cet objectif, nous transformons les communications HLA en événements utilisables par le système de reconnaissance de chroniques. Nous validons nos choix en développant un composant d’analyse pour une simulation existante, le projet Aéroport Du Futur (Onera). Pour simpliﬁer la construction de composants d’analyse, nous avons développé une extension de Genesis (un outil de développement de simulations HLA) pour engendrer automatiquement un composant d’analyse : le composant HLA engendré est intégré directement dans une simulation HLA sans modiﬁcation de la simulation
The goal is to provide a simple way to analyse (e. G. To search (un)desired activities, to measure activity duration,. . . ) High Level Architecture (HLA) distributed simulations. To this end we chose chronicle recognition, and we describe searched activities by chronicles (using the CRS/Onera language). The ﬁrst step is a formalmodelisation of the used chronicle recognition system(CRS/Onera). So as to model chronicle recognition we ﬁrst compare the expressivity of different kinds of automata. We chose Coloured Petri nets with which we could produce an elegant and modular model. We prove, for some constructions, the correctness of the built Petri nets. Then we model an event managing system in coloured Petri nets. Using this model, we validate the behaviour of the recognition tool e. G. For forbidden chronicle expressions, and chronicles with event repetitions. After this validation of CRS/Onera, we facilitate its integration in HLA simulation in order to detect activities. So we choose to integrate CRS/Onera in a HLA component (federate). In order to achieve this goal we transform HLA communications to events usable for the chronicle recognition system. We validate our choices with the development of an analysis component for an existing simulation, the Future Airport project built by Onera. In order to further simplify the building of analysis components, we developed an extension for Genesis (a tool for developing HLA simulation) to generate automatically an analysis component. To simplify the use of an analysis component, an HLA component is generated that is integrated directly in a HLA simulation without modiﬁcation of the simulation

APA, Harvard, Vancouver, ISO, and other styles

37

Aber, Naïm. "Abstraction et analyse de l'espace des états des réseaux de Pétri temporels." Paris 13, 2013. http://scbd-sto.univ-paris13.fr/secure/edgalilee_th_2013_aber.pdf.

Full text

Abstract:

Les réseaux de Petri temporels sont largement utilisés pour la spécification des systèmes où le temps est exprimé explicitement. Le principal défi pour l’analyse de tels systèmes est de pouvoir construire une abstraction finie de l’espace d’états qui préserve des familles de propriétés que l’on veut vérifier. De plus, les algorithmes de construction doivent être optimaux en termes de temps de calcul et d’espace mémoire. Notre première contribution dans cette thèse est un nouveau graphe appelé Graphe des Agrégats Temporisés (TAG) qui permet l’abstraction du comportement des réseaux de Petri temporels bornés avec une sémantique de tir forte. Le principal apport de notre approche, comparée aux approches existantes, est l’encodage des informations temporelles. En effet,chaque noeud du TAG comporte des informations temporelles permettant de calculer les délais minimum et maximum écoulés sur chaque chemin du graphe. Le TAG est fini pour les réseaux de Petri temporels bornés, et permet de préserver les séquences et les marquages accessibles ainsi que la vérification des propriétés sur les événements ou sur les états. Nous proposons dans la deuxième contribution des algorithmes pour la vérification des formules TCTL et prouvons leur correction
Time Petri nets (TPN models) allow the specification of real-time systems involving explicit timing constraints. The main challenge of the analysis of such systems is to construct, with as few resources (time and space), a coarse abstraction preserving timed properties. We propose a new finite graph, called Timed Aggregate Graph (TAG), abstracting the behaviour of bounded TPNs with strong time semantics. The main feature of this abstract representation compared to existing approaches is the encoding of the time information. This is done in a pure way within each node of the TAG allowing to compute the minimum and maximum time elapsed in every path of the graph. The TAG preserves runs and reachable states of the corresponding TPN and allows for verification of both event- and state-based properties. In the second contribution, we propose the appropriate algorithms for checking TCTL formulae and prove the correction of these algorithms

APA, Harvard, Vancouver, ISO, and other styles

38

Ponce, de León Hernan. "Testing concurrent systems through event structures." Thesis, Cachan, Ecole normale supérieure, 2014. http://www.theses.fr/2014DENS0035/document.

Full text

Abstract:

Les systèmes logiciels complexes sont omniprésents dans notre vie quotidienne. De ce fait, un dysfonctionnement peut occasionner aussi bien une simple gêne qu'un danger mettant en péril des vies humaines. Le test est l'une des techniques les plus répandues (en particulier dans l'industrie) pour détecter les erreurs d'un système. Lorsque le cahier des charges d'un système est décrit par une spécification formelle, le test de conformité est utilisé pour garantir un certain niveau de confiance dans la correction d'une implémentation de ce système - dans ce cadre, la relation de conformité formalise la notion de correction. Cette thèse se focalise sur le test de conformité pour les systèmes concurrents. Le test de conformité pour les systèmes concurrents utilise principalement des modèles qui interprètent la concurrence par des entrelacements. Néanmoins, cette approche souffre du problème de l'explosion de l'espace d'états et elle n'offre pas la possibilité de tester certaines propriétés de la spécification telle que l'indépendance entre actions. Pour ces raisons, nous utilisons une sémantique d'ordres partiels pour la concurrence. De plus, nous proposons une nouvelle sémantique qui permet à certaines actions concurrentes d'être entrelacées et en force d'autres à être implémentées indépendamment. Nous proposons une généralisation de la relation de conformité ioco où les spécifications sont des réseaux de Petri et leur sémantique d'ordres partiels est donnée par leur dépliage. Cette relation de conformité permet de préserver l'indépendance, dans l'implémentation, des actions spécifiées comme concurrentes. Nous présentons un cadre de test complet pour cette relation. Nous définissons la notion de cas de test globaux gérant la concurrence, réduisant ainsi non seulement la taille des cas de test mais aussi celle de la suite de tests. Nous montrons comment les cas de test globaux peuvent être construits à partir du dépliage de la spécification en s'appuyant sur une traduction SAT, et nous réduisons le problème de la sélection de tests à la sélection d'un préfixe fini de ce dépliage : nous définissons différents critères de sélection à partir de la notion d'événement limite (cut-off event). Enfin, en supposant que chaque processus d'un système distribué possède une horloge locale, nous montrons que la conformité globale peut être testée dans une architecture de test distribuée en utilisant seulement des testeurs locaux ne communiquant pas entre eux
Complex systems are everywhere and are part of our daily life. As a consequence, their failures can range from being inconvenient to being life-threatening. Testing is one of the most widely accepted techniques (especially in industry) to detect errors in a system. When the requirements of the system are described by a formal specification, conformance testing is used to guarantee a certain degree of confidence in the correctness of an implementation- in this setting a conformance relation formalizes the notion of correctness. This thesis focuses on conformance testing for concurrent systems. Conformance testing for concurrent system has mainly focused on models that interpret concurrency by interleavings. This approach does not only suf- fer from the state space explosion problem, but also lacks the ability to test properties of the specification such as independence between actions. For such reasons, we focus not only on partial order semantics for concurrency, but also propose a new semantics that allows to interleave some actions while forcing others to be implemented as independent. We propose a generalization of the ioco conformance relation, based on Petri nets specifications and their partial order semantics given by their unfoldings, preserving thus independence of actions from the specification. A complete testing framework for this conformance relation is presented. We introduce the notion of global test cases which handle concurrency, reducing not only the size of the test case, but also the number of tests in the test suite. We show how global test cases can be constructed from the unfolding of the specification based on a SAT encoding and we reduce the test selection problem to select a finite prefix of such unfolding: different testing criteria are defined based on the notion of cut-off events. Finally, we show that assuming each process of a distributed system has a local clock, global conformance can be tested in a distributed testing architecture using only local testers without any communication

APA, Harvard, Vancouver, ISO, and other styles

39

Pocci, Marco. "Test and diagnosis of discrete event systems using Petri nets." Thesis, Aix-Marseille, 2013. http://www.theses.fr/2013AIXM4336/document.

Full text

Abstract:

Le test d’identification d’état d’un système à événement discret (SED) a pour but d’en identifier l’état final, lorsque son état initial est inconnu. Une solution classique à ce problème, en supposant que le SED n’ait pas de sorties observables, consiste à déterminer une séquences de synchronisation, c.à-d., une séquence d’événements d’entrée qui conduit le SED sur un état connu. Ce problème a été résolu dans les années 60’ à l’aide des automates. L’objectif principal de cette thèse est d’utiliser les réseaux de Petri (RdP) pour obtenir une résolution plus optimal de ce problème et pour une plus large classe de systèmes.Initialement, nous montrons que la méthode classique peut être aisément étendue aux RdP synchronisés. Pour cette classe de réseaux non-autonomes, toute transition est associée à un événement d’entrée.L’approche proposée est générale, dans la mesure où elle s’applique à des RdP bornés arbitraires. Cependant, elle engendre le problème d’explosion combinatoire du nombre d’états. Pour obtenir des meilleures solutions, nous considérons une classe spéciale de RdP : les graphes d’état (GdE). Pour ces réseaux, nous considérons d’abord les GdE fortement connexes et proposons des approches pour la construction de SS, qui exploitent les propriétés structurelles du réseau en évitant ainsi une énumération exhaustive de l’espace d’état. Ces résultats s’étendent aux GdE non fortement connexes et à tout RdP synchronisé composé de GdE. Enfin, nous considérons la classe des RdP non bornés et proposons des séquences qui synchronisent le marquage des places non bornées. Une boîte à outils fournit toutes les approches décrites et est appliquée à des différents bancs d’essai
State-identification experiments are designed to identify the final state of a discrete event system (DES) when its initial state is unknown. A classical solution, assuming the DES has no observable outputs, consists in determining a synchronizing sequence (SS), i.e., a sequence of input events that drives the system to a known state. This problem was essentially solved in the 60’ using automata. The main objective of this thesis is to use Petri nets (PNs) for solving the state-identification problem more efficiently and for a wider class of systems.We start showing that the classical SS construction method based on automata can be easily applied to synchronized PNs, a class of non-autonomous nets where each transition is associated with an input event. The proposed approach is fairly general and it works for arbitrary bounded nets with a complexity that is polynomial with the size of the state space. However, it incurs in the state-space explosion problem.Looking for more efficient solutions, we begin by considering a subclass of PNs called state machines (SMs). We first consider strongly connected SMs and propose a framework for SS construction that exploits structural criteria, not requiring an exhaustive enumeration of the state space of the net. Results are further extended to larger classes of nets, namely non strongly connected SMs and nets containing SM subnets. Finally we consider the class of unbounded nets that describe infinite state systems: even in this case we are able to compute sequences to synchronize the marking of bounded places. A Matlab toolbox implementing all approaches previously described has been designed and applied to a series of benchmarks

APA, Harvard, Vancouver, ISO, and other styles

40

Riviere, Nicolas. "Modélisation et analyse temporelle par réseaux de Petri et logique linéaire." Phd thesis, INSA de Toulouse, 2003. http://tel.archives-ouvertes.fr/tel-00134974.

Full text

Abstract:

L'objectif de cette thèse est de contribuer à l'élaboration de méthodes d'aide à la conception de systèmes coopératifs en prenant en compte les contraintes temporelles de manière quantitative. L'approche développée est fondée sur les réseaux de Petri, la logique linéaire et les graphes de contraintes temporelles. C'est une approche orientée « événements » et non orientée « états » comme c'est souvent le cas dans les approches fondées sur les réseaux de Petri. Elle est décomposée en deux étapes : une étape d'analyse « qualitative » et une étape d'analyse « quantitative ». La première consiste à obtenir les relations de causalité entre les événements appartenant à un scénario donné. L'équivalence entre un arbre de preuve en logique linéaire et le processus fini obtenu par dépliage d'un réseau de Petri à partir du même marquage initial montre que ces relations sont des relations de précédence. L'introduction de la notion de séquent caractéristique permet de mettre en Suvre une approche compositionnelle des processus à partir des règles du calcul des séquents. La deuxième étape consiste à passer du graphe décrivant les relations de précédence à un graphe de contraintes temporelles exprimant de façon linéaire l'ensemble des contraintes temporelles quantitatives que doivent vérifier les dates des franchissements des transitions dans un scénario. Il devient ainsi possible d'exploiter tous les résultats des techniques classiques d'analyse et de propagation de contraintes. Cette démarche est complètement cohérente avec les réseaux de Petri p-temporels mais difficilement compatible avec les t-temporels car ils engendrent des ensembles de contraintes qui sont plus complexes. Nous avons illustré cette démarche par un problème simple d'ordonnancement de documents multimédias. Nous avons par la suite montré comment, pour les réseaux de Petri t-temporels, nous pouvions calculer les dates de franchissements et les durées de séjour des jetons dans les places en restant sous une fo rme symbolique dans le cadre de la sémantique faible.

APA, Harvard, Vancouver, ISO, and other styles

41

Quivrin-Pfister, Wilfried. "Des bisimulations de places pour la réduction des réseaux de Petri." Phd thesis, Grenoble INPG, 1995. http://tel.archives-ouvertes.fr/tel-00005059.

Full text

Abstract:

Cette thèse concerne une nouvelle méthode de réduction des réseaux de Petri. Le problème de la réduction des réseaux a d'abord été considéré comme le moyen de réduire l'espace des états sans modifier un certain nombre de propriétés (telles que "être borne", "être vivant", etc) afin de faciliter leur étude. Nous nous placons ici dans une toute autre optique, puisque nous allons chercher une méthode de réduction non pas en voulant conserver un ensemble de propriétés, mais préservant le comportement du réseau. Dans les premières parties, nous recherchons la relation la plus grande possible qui soit une équivalence sur les places du réseaux nous permettant de les fusionner et telle que le réseau réduit soit bisimilaire au réseau original. Nous montrons que la bisimulation de places vérifie ces contraintes et qu'il existe des algorithmes efficaces (polynomiaux) pour la calculer. Dans la suite, des cas d'extensions classiques des réseaux (arcs inhibiteurs) comme des équivalences (bisimulations "observationnelle") sont abordés. La dernière partie de la thèse s'intéresse à l'équivalence de propriétés entre le réseau initial et le réseau quotient. Ce travail se termine par la présentation succincte du logiciel Petris qui met en oeuvre les différents algorithmes.

APA, Harvard, Vancouver, ISO, and other styles

42

Biaz, Saâd. "Réseaux de Petri appliqués à la conception de systèmes numériques rapides." Nancy 1, 1989. http://www.theses.fr/1989NAN10276.

Full text

Abstract:

Élaboration d'une méthode pour concevoir des architectures de systèmes numériques adaptés à un algorithme avec construction d'un graphe de transmission de données et d'un graphe de précédence de tâches afin d'obtenir un réseau de Petri

APA, Harvard, Vancouver, ISO, and other styles

43

Bourdeaud'huy, Thomas. "Techniques d'abstraction pour l'analyse et la synthèse de réseaux de Petri." Ecole Centrale de Lille, 2004. http://www.theses.fr/2004ECLI0003.

Full text

Abstract:

Le croisement de concepts issus de la logique, de la recherche opérationnelle et de ï'automatique discrète nous. Permet de nous intéresser au problème de l'explosion combinatoire sous des angles d'attaque nouveaux, pour proposer finalement un ensemble de techniques d'abstraction pour l'analyse et la synthèse de réseaux de Petri. Pour l'analyse, nous proposons une abstraction du comportement des RdPs. Le résultat principal concerne la définition d'un modèle incrémentai permettant de capturer le comportement du RdP étudié. Ce modèle permet la formulation de propriétés dites positives dont l'expressivité s'étend aux problématiques d'accessibilité et de sûreté. Nous le traduisons ensuite en un problème d'optimisation combinatoire, et proposons plusieurs modèles opérationnels et techniques complémentaires permettant d'améliorer les performances pratiques de résolution. Dans le cadre de l'étude des RdPs bornés, nous contribuons également à la défmition formelle des paramètres de profondeur séquentielle et intrinsèque, qui permettent de garantir les propriétés de décidabilité de nos algoritlnnes. Pour la synthèse, nous développons une abstraction de la structure des RdPs. Nous utilisons cette abstraction pour présenter une approche de conception incrémentale originale fondée sur la notion d'exigences de fonctionnement. Cette démarche exploratoire consiste à intégrer dans une même méthodologie des techniques de spécification formelle et de vérification. Les exigences sont traduites en termes de contraintes sur les éléments d'une structure appelée RdP1 partieL Des outils de résolution de contraintes permettent ensuite de générer les réseaux satisfaisant les exigences de départ.

APA, Harvard, Vancouver, ISO, and other styles

44

Wu, Changshun. "Séquences de synchronisation pour les réseaux de Petri synchronisés non bornés." Thesis, Aix-Marseille, 2018. http://www.theses.fr/2018AIXM0717.

Full text

Abstract:

L'un des problèmes fondamentaux de test pour les systèmes à événements discrets (SEDs) est l'identification d'un état final, c'est-à-dire, étant donné un système dont l'état courant est inconnu, trouver une séquence d'événements d'entrée pouvant le conduire à un état connu. Les séquences de synchronisation (SS), sans information de sortie, sont une solution classique à ce problème. Dans cette thèse, nous étudions la détermination des SS pour des systèmes modélisés par des réseaux de Petri synchronisés (SynPN) non bornés, une classe de réseaux de Petri avec des entrées. Dans la première partie de cette thèse, nous développons deux méthodes: 1) construction d'une représentation finie, appelée improved modified coverability graph (IMCG), pour d'écrire exactement l'espace d'états infini d'un 1-place-unbounded SynPN; 2) conversion d'un 1-place-unbounded SynPN en un automate pondéré (WA) fini et sauf équivalent. Les deux graphes sont ainsi potentiellement des outils puissants pour déterminer les SS pour une telle sous-classe de réseaux de Petri. Dans la seconde partie de cette thèse, nous développons des algorithmes de calcul pour deux problèmes de synchronisation de localisation dans le cas où l'IMCG ou le WA sont déterministes : synchronisation sur un seul nœud et synchronisation sur un sous-ensemble de nœuds de ces deux graphes. L'avantage de ces algorithmes de calcul est de réduire le calcul sur les graphes globaux (IMCG ou WA) à celui du plus petit sous-graphe: la composante fortement connectée ergodique peut réduire l'effort de calcul mais peut également être appliquée lorsque le IMCG ou le WA équivalent déterministes ne sont pas fortement connexes
One of the fundamental testing problems for discrete event systems (DESs) is the identification of a final state, i.e., given a system whose current state is unknown, find an input sequence that can drive it to a known state. Synchronizing sequences (SSs), without output information, are one conventional solution to this problem. In this thesis, we address the computation of SSs for systems modeled by unbounded synchronized Petri nets (SynPNs), a class of Petri nets with inputs. In the first part of this thesis, we utilize two methods: 1) construct a finite representation, called improved modified coverability graph (IMCG), to exactly describe the infinite state space of a 1-place-unbounded SynPN; 2) convert a 1-place-unbounded SynPN into an equivalent finite location weighted automaton (WA) with safety conditions. Both graphs are thus, potentially, useful tools to compute SSs for such subclass of nets. In the second part of this thesis, we develop computation algorithms for two location synchronization problems in the case either the IMCG or the WA is deterministic: synchronization into a single node and synchronization into a subset of nodes of these two graphs. The advantage of these computation algorithms consists in reducing the computation on the global graphs (IMCGs or WAs) to the one on the smaller subgraph: the ergodic strongly connected component (SCC), which can reduce the computational effort and furthermore can also be applied when the converted deterministic IMCG or WA is not strongly connected

APA, Harvard, Vancouver, ISO, and other styles

45

Trèves, Nicolas. "Le calcul d'invariants dans les réseaux de Pétri à prédicats transitions unaires." Paris 11, 1986. http://www.theses.fr/1986PA112264.

Full text

Abstract:

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/TransitionsUnaires (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
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

APA, Harvard, Vancouver, ISO, and other styles

46

Bouziane, Zakaria. "Algorithmes primitifs récursifs et problèmes EXPSPACE-Complets dans les réseaux de Petri cycliques." Cachan, Ecole normale supérieure, 1996. http://www.theses.fr/1996DENS0023.

Full text

Abstract:

Nous présentons, dans cette thèse, des résultats de complexité pour les problèmes de vérification (l'accessibilité, la couverture, le boundedness, la rationalité, la vivacité, l'inclusion et l'équivalence) de certaines classes de réseaux de Petri (réseaux cycliques, structurellement cycliques et réversibles). Ces résultats nous permettent de dériver d'autres résultats de complexité dans le domaine de l'algorithmique des variétés algébriques (semi groupes commutatifs). Nous calculons aussi des bornes supérieures pour les solutions minimales des systèmes diophantiens linéaires ce qui nous permet de montrer que le problème de l'accessibilité pour deux classes de réseaux de Petri (réseaux conservatifs et réseaux acycliques) est en espace 2#c#. #n.

APA, Harvard, Vancouver, ISO, and other styles

47

Sarri, Patrick. "Stabilisation optimale des systèmes à événements discrets à structure vectorielle : application à la sécurité opérationnelle des systèmes de production." Lyon, INSA, 1999. http://www.theses.fr/1999ISAL0016.

Full text

Abstract:

Nous proposons d'exploiter un modèle de système à événements discrets (SED) à structure vectorielle (VDES) dans le cadre de la commande logique des SED basé sur le concept d'événements contrôlables initié par Ramadge et Wonham (RW). Li et Wonham ont formalisé le modèle VDES dans le contexte de la théorie du contrôle. L'espace d'état d'un VDES est un espace vectoriel dont les variables d'états à valeurs discrètes peuvent être représentées par des jetons dans des places à l'instar des réseaux de Petri. La contrainte de positivité qui est figée dans le cas des réseaux de Petri, est généralisée et définie pour chaque modèle dans le cas des VDES. La transition d'état associée à chaque événement est représentée par un vecteur déplacement dans l'espace d'état ce qui confère aux VDES une structure plus riche par rapport au modèle à automates. L'objectif de nos travaux est d'exploiter cette structure afin d'obtenir des solutions efficaces aux problèmes de la stabilisation et du contrôle optimal de trajectoires et de les appliquer à la sécurité opérationnelle des systèmes de production. La stabilisation consiste à conduire un système depuis un état initial vers un sous-ensemble d'états prédéfinis. Ainsi après avoir formalisé la stabilisation et le contrôle optimal de trajectoire dans le cadre des VDES et proposé un algorithme de synthèse en ligne de commande stabilisante/optimisante, nous présentons en application des techniques issues de la sécurité opérationnelle pour la récupération en cas de défaillance ou de dysfonctionnement dans le procédé. A titre d'illustration, ces techniques sont appliquées à la plate forme expérimentale de l'Atelier Inter-Etablissements de Productique (AIP) Rhône Alpes Ouest Lyon
We propose a vector discrete event systems approach (VDES) based on logic Supervisory Control Theory initiated by Ramadge and Wonham (RW). Li and Wonham specialize the control theory of discrete-event systems (DES) to a setting of vector addition systems. The state space of a VDES is a Z module under vector addition and multiplication by integers and variable states represent token as in Petri net graph. The Petri net non-negativity constraint is generalized in the case of VDES and defined for each model. For each event, the state transition function is a displacement function in the state space. We propose to exploit the VDES structure in order to obtain efficient solution to the problem of stabilization and optimal trajectory control in application to automated manufacturing system operational safety. The notion of stabilization is concerned with the possibility of driving a process from arbitrary initial states to a prescribed subset of state set and then keeping it there indefinitely. We formalize the stabilization and optimal control problem for VDES and present an algorithm to synthesize a real time supervisor. Furthermore we present an application based on the Operational Safety concept to design and synthesize optimally suited reactivity control over critical failures so as to ensure degraded functioning. The concepts developed have been applied to the fairly complex manufacturing system of the "Atelier Inter-Etablissements de Productique" (AIP) Rhône Alpes, Ouest Lyon (France)

APA, Harvard, Vancouver, ISO, and other styles

48

Cardoso, Janette. "Sur les réseaux de pétri à marquages flous." Toulouse 3, 1990. http://www.theses.fr/1990TOU30171.

Full text

Abstract:

Ce mémoire concerne l'élaboration d'un modèle combinant les réseaux de Petri à Objets, la théorie des possibilités et les notions de connaissance temporelle floue en vue d'une application à la surveillance des ateliers de fabrication automatisés, au niveau de la coordination globale. En effet, une surveillance efficace et capable de tolérer les interventions humaines nécessite de pouvoir décrire des situations ou l'état du système n'est pas connu avec certitude. La théorie des possibilités, en associant des distributions de possibilités aux divers états permet d'appréhender ce phénomène, en augmentant le nombre d'évènements considérés comme acceptables. Un contrôle flexible de l'exécution d'un plan de fabrication nécessite la manipulation de connaissances temporelles floues. Enfin, la modélisation des contraintes de séquencement découlant des gammes de fabrication et des allocations des machines implique l'utilisation des réseaux de Petri. L'idée présentée dans ce travail est d'introduire les notions de marquages imprécis et flou dans la théorie des réseaux de Petri. En cas d'incident, en plus du marquage courant pour lequel la localisation des jetons est certaine, on introduit un certain nombre de jetons dont la localisation est incertaine. A titre d'exemple est présenté l'utilisation du réseau de Petri avec marquage flou dans le cadre de la surveillance et de la reprise dans un atelier de fabrication automatisé.

APA, Harvard, Vancouver, ISO, and other styles

49

Saives, Jérémie. "Identification Comportementale "Boîte-noire" des Systèmes à Evénements Discrets par Réseaux de Petri Interprétés." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLN018/document.

Full text

Abstract:

Cette thèse contribue à l’identification de modèles compacts et expressifs de Systèmes à Evénements Discrets (SED) réactifs, à des fins de rétro-conception ou de certification. L’identification est passive, et boîte-noire, la connaissance se limitant aux signaux d’entrées/sorties du système. Les Réseaux de Petri Interprétés (RdPI) permettent de modéliser à la fois le comportement observable (causalités entrées/sorties observées directement), et le comportement non observable du système (évolutions de variables internes). Cette thèse vise à identifier des modèles RdPI à partir d’une séquence observée de vecteurs entrées/sorties. Notamment, l’enjeu étant de traiter des systèmes concurrents de taille réaliste, l’approche développée permet le passage à l’échelle de résultats précédents.La construction de la partie observable est d’abord améliorée par l’ajout d’un filtre. Celui-ci détecte et supprime les synchronisations parasites causées par le contrôleur en présence de systèmes concurrents. Une nouvelle approche est ensuite proposée pour découvrir la partie non observable, basée sur l’utilisation de projections, et garantissant la reproductibilité du comportement observé malgré la concurrence. Une heuristique permet de construire un modèle satisfaisant pour la rétro-ingénierie, à coût de calcul limité. Enfin, une approche distribuée est proposée pour réduire davantage le coût de calcul, en partitionnant automatiquement le système en sous-systèmes. L’effet cumulatif de ces contributions est illustré par l’identification de RdPI sur un système de taille raisonnable, validant leur efficacité
This thesis proposes a method to identify compact and expressive models of closed-loop reactive Discrete Event Systems (DES), for reverse-engineering or certification. The identification is passive, and blackbox, accessible knowledge being limited to input/output signals. Interpreted Petri Nets (IPN) represent both the observable behaviour (direct input/output causalities) and the unobservable behaviour (internal state evolutions) of the system. This thesis aims at identifying IPN models from an observed sequence of I/O vectors. The proposed contributions extend previous results towards scalability, to deal with realistic systems who exhibit concurrency.Firstly, the construction of the observable part of the IPN is improved by the addition of a filter limiting the effect of concurrency. It detects and removes spurious synchronizations caused by the controller. Then, a new approach is proposed to improve the discovery of the unobservable part. It is based on the use of projections and guarantees the reproduction of the observed behaviour, despite concurrency. An efficient heuristic is proposed to compute a model adapted to reverse-engineering, limiting the computational cost. Finally, a distributed approach is proposed to further reduce the computational cost, by automatically partitioning the system into subsystems. The efficiency of the cumulative effect of these contributions is validated on a system of realistic size

APA, Harvard, Vancouver, ISO, and other styles

50

Fronc, Lukasz. "Compilation de réseaux de Petri : modèles haut niveau et symétries de processus." Thesis, Evry-Val d'Essonne, 2013. http://www.theses.fr/2013EVRY0034/document.

Full text

Abstract:

Cette thèse s'intéresse à la vérification de systèmes automatisables par model-checking. La question sous-jacente autour de laquelle se construit la contribution est la recherche d'un compromis entre différents objectifs potentiellement contradictoires : la décidabilité des systèmes à vérifier, l'expressivité des formalismes de modélisation, l'efficacité de la vérification, et la certification des outils utilisés. Dans ce but, on choisit de baser la modélisation sur des réseaux de Petri annotés par des langages de programmation réels. Cela implique la semi-décidabilité de la plupart des questions puisque la responsabilité de la terminaison est remise entre les mains du modélisateur (tout comme la terminaison des programmes est de la responsabilité du programmeur). Afin d'exploiter efficacement ces annotations, on choisit ensuite une approche de compilation de modèle qui permet de générer des programmes efficaces dans le langage des annotations, qui sont alors exécutées de la manière la plus efficace. De plus, la compilation est optimisée en tirant partie des spécificités de chaque modèle et nous utilisons l'approche de model-checking explicite qui autorise cette richesse d'annotations tout en facilitant le diagnostique et en restant compatible avec la simulation (les modèles compilés peuvent servir à de la simulation efficace). Enfin, pour combattre l'explosion combinatoire, nous utilisons des techniques de réductions de symétries qui permettent de réduire les temps d'exploration et l'espace mémoire nécessaire
This work focuses on verification of automated systems using model-checking techniques. We focus on a compromise between potentially contradictory goals: decidability of systems to be verified, expressivity of modeling formalisms, efficiency of verification, and certification of used tools. To do so, we use high level Petri nets annotated by real programming languages. This implies the semi-decidability of most of problems because termination is left to the modeler (like termination of programs is left to the programmer). To handle these models, we choose a compilation approach which produces programs in the model annotation language, this allows to execute them efficiently. Moreover, this compilation is optimizing using model peculiarities. However, this rich expressivity leads to the use of explicit model-checking which allows to have rich model annotations but also allows to easily recover errors from verification, and remains compatible with simulation (these compiled models can be used for efficient simulation). Finally, to tackle the state space explosion problem, we use reduction by symmetries techniques which allow to reduce exploration times and state spaces

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Réseaux de Petri Lots'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles