Structuration des systèmes de transitions-applications au contrôle du parallélisme par Files Fifo
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
We present a structure for transition systems such that mains algorithms on Petri nets can be generalized to structured transition systems. We define the reduced tree of a structured transition system; it allows deciding the finiteness of the reachability set and of the language of firing sequences. The definition of the cover ability graph, introduced by Karp and Miller for parallel program schemata, is extended for well-structured transition systems. We show that quasi-liveness and deadlock freedom are two decidable problems in the framework of well-structured transition systems. We introduce the notion of structured transition systems isomorphism and we show that the finite product of structured transition systems is still a structured transition system. We then apply these results for two classes of structured Fifo nets called monogeneous nets and free choice nets. It is shown that any monogeneous net is simulated by a Petri net intersected with a finite automaton; there also exists a relation between free choice net language and its associated colored Petri net language: this language is included in all permutations of the free choice net language. These two relations allow deciding the liveness of a monogeneous net or a free choice net. Others results about the expression power of Fifo nets, control of processes by finite automaton and formal languages theory of Petri nets and Fifo nets are also given.
Abstract FR:
Nous présentons une structure sur les systèmes de transitions telle que les principaux algorithmes existant sur les réseaux de Petri se généralisent aux systèmes de transitions structurés. L'arborescence réduite d'un système de transitions structuré est définie; elle permet de décider la finitude de l'ensemble des états accessibles et de l'ensemble des séquences franchissables. La définition du graphe de couverture, introduite par Karp et Miller pour les schémas de programmes parallèles, est généralisée aux systèmes de transitions bien structurés. Pour ceux-ci on montre que la quasi-vivacité et l'absence de blocage sont deux problèmes décidables. Nous introduisons la notion d'isomorphisme de systèmes de transitions structurés et nous montrons que le produit fini de systèmes de transitions structurés est encore un système de transitions structuré. Nous appliquons ensuite ces résultats généraux à deux classes de réseaux à files structurés: les réseaux monogènes et les réseaux à choix libre. Il est de plus montré qu'un réseau monogène est simulé par un réseau de Petri intersecté par un automate fini; il existe aussi une relation entre le langage d'un réseau à choix libre et le langage de son réseau de Petri coloré associé: celui-ci est inclus dans les permutations du langage du réseau à choix libre. Ces deux relations permettent de décider la vivacité d'un réseau monogène ou à choix libre. D'autres résultats concernant la puissance d'expression des réseaux à files, le contrôle de processus par automate fini et la théorie des langages de réseaux de Petri et de réseaux à files sont aussi exposés.