ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 22/4 - 2003  - pp.435-459  - doi:10.3166/tsi.22.435-459
TITRE
Analyse des réseaux temporels. Calcul des classes en O(n2) et des temps de chemin en O(m ×n)

RÉSUMÉ
Le modèle de Merlin est un réseau de PETRI qui associe un intervalle de temps à chaque transition. Pour analyser ce modèle, Menasche, Berthomieu et Diaz ont proposé une approche qui génère une contraction de son espace infini d’états ([MEN 82], [BER 91], [DIA 01]). Cette contraction appelée graphe des classes est finie si et seulement si le modèle est borné. La complexité connue de calcul de chaque successeur d’une classe est O(n3), où n est le nombre de transitions sensibilisées pour le marquage de la classe [DIA 01]. Nous montrons ici comment réduire cette complexité pour atteindre O(n2). Nous développons, ensuite, un algorithme simple qui calcule, en parcourant un chemin (ou un cycle) du graphe des classes, les temps minimal et maximal d’exécution de la séquence du chemin. La complexité de cet algorithme est O(m×n), où m est la longueur du chemin et n est le nombre de transitions sensibilisées dans la plus grande classe (en nombre de transitions sensibilisées) du chemin.


ABSTRACT

Merlin’s model is a PETRI net completed by time intervals associated with transitions. To analyse this model, Menasche, Berthomieu and Diaz have proposed an approach that generates one contraction of its infinite state space ([MEN 82], [BER 91], [DIA 01]). This contraction, called state class graph, is finite if and only if the model is bounded. The known complexity of computing each state class is O(n3), where n is the number of transitions enabled for [DIA 01]. We show, here, how to reduce this complexity to reach O(n2). We develop afterwards a simple algorithm that computes, by exploring one path (or a cycle) of the state class graph, the minimal and maximal running times of the path sequence. The complexity of the algorithm is O(m ×n), m is length of the path and n is the number of transitions enabled in the biggest class (in number of enabled transitions) of the path.



AUTEUR(S)
Hanifa BOUCHENEB, John MULLINS

Reçu le 3 juin 2002.    Accepté le 4 février 2003.

MOTS-CLÉS
modèle de Merlin, graphe des classes d’états, temps de chemin, temps de cycle.

KEYWORDS
Merlin’s model, state class graph, path time, cycle time.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (350 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier