Séquentialisation du comportement des réseaux de Petri temporisés

0422087 - MÚ 2014 RIV FR fre J - Journal Article
Boimond, J.-L. - Komenda, Jan - Lahaye, S.
Séquentialisation du comportement des réseaux de Petri temporisés.
[Sequentialization of timed Petri net behaviours.]
Journal Européen des Systèmes Automatisés. Roč. 47, 1-3 (2013), s. 139-154. ISSN 1269-6935.
[Modélisation des Systèmes Réactifs (MSR) 2013. Rennes, 13.11.2013-15.11.2013]
R&D Projects: GA ČR(CZ) GAP103/11/0517
Institutional support: RVO:67985840
Keywords : timed Petri nets * (max,+) automata * race policy
Subject RIV: BA - General Mathematics
http://jesa.revuesonline.com/article.jsp?articleId=18769

Ce papier s’intéresse à la séquentialisation des séries formelles à coefficients dans le semi-anneau (R {−∞}, max, +) qui représentent le comportement de réseaux de Petri temporisés bornés. Des méthodes existent pour modéliser les réseaux de Petri temporisés saufs par des automates (max,+). Les automates résultants sont presque toujours non déterministes et les procédures de déterminisation existantes ne peuvent que très rarement leur être appliquées. Ceci proscrit l’utilisation de certains résultats, notamment pour l’évaluation de performances et la commande. Nous présentons un semi-algorithme pour obtenir des automates (max,+) déterministes en se basant sur la sémantique des réseaux de Petri temporisés. Les automates obtenus peuvent être infinis, mais nous proposons une condition suffisante pour assurer que le semi-algorithme termine et conduise à un automate (max,+) déterministe fini. Lorsque le réseau considéré ne peut être séquentialisé (car la procédure ne termine pas), nous proposons de restreindre le comportement logique du réseau de sorte à assurer la séquentialisation.

In this paper we are interested in sequentialization of formal power series with coefficients in the semiring (R {−∞}, max, +) which represent the behavior of timed Petri nets. Several approaches make it possible to derive nondeterministic (max,+) automata modeling safe timed Petri nets. Their nondeterminism is a serious drawback since determinism is a crucial property for numerous results on (max,+) automata (in particular, for applications to performance evaluation and control) and existing procedures for determinization succeed only for restrictive classes of (max,+) automata. We present a natural semi-algorithm for determinization of behaviors based on the semantics of timed Petri nets. The resulting deterministic (max,+)-automata are often infinite, but a sufficient condition is proposed to ensure that the semi-algorithm terminates and leads to a finite state deterministic (max,+)-automaton. Moreover, if the net cannot be sequentialized we propose a restriction of its logical behavior so that the sufficient condition becomes satisfied for the restricted net.
Permanent Link: http://hdl.handle.net/11104/0228302