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 28/9 - 2009  - pp.1143-1170  - doi:10.3166/tsi.28.1143-1170
TITRE
Optimisation de la construction d'une approximation de l'espace d'état des systèmes préemptifs

RÉSUMÉ
Nous proposons dans cet article un algorithme permettant de construire efficacement la plus fine surapproximation DBM du graphe des classes d'un système préemptif modélisé au moyen d'un réseau de Petri temporel à arcs inhibiteurs. Pour ce faire, nous exprimons chaque classe du graphe approché par la paire (M, D) où M est un marquage et D est un ~ ~ système représentant toutes les contraintes DBM même celles redondantes. Nous proposons un algorithme calculant le système D directement dans sa forme normale, sans nécessiter le ~ calcul du polyèdre intermédiaire. Nous réduisons ainsi considérablement le coût de calcul d'une classe, et nous éliminons les défauts d'implémentation constatés pour les autres approches. Nous discutons en outre comment déterminer à partir du graphe obtenu les propriétés linéaires et quantitatives du modèle. Nous présentons enfin les résultats des expérimentations comparant les implémentations des différentes approches.


ABSTRACT
We present in this paper an algorithm allowing an efficient computation of the tightest DBM over-approximation of the state class graph of preemptive systems modeled by using Time Petri Nets with inhibitor arcs. For this effect, we express each class of the approximated graph as a pair (M, D ), where M is a marking and D is the system of all DBM ~ ~ inequalities even the redundant ones. We thereby make it possible to compute the system D ~ straightforwardly in its normal form, without requiring to compute the intermediary polyhedra. Hence, we succeed to reduce appreciably the computation cost of a class, and to remove the implementation dysfunctions reported for other approaches. We also discuss how to determine from the graph linear and quantitative properties of the model. Finally, we give some experimental results that compare the implementations of the different approaches.


AUTEUR(S)
Abdelkrim ABDELLI

MOTS-CLÉS
systèmes préemptifs, DBM, polyèdre, réseau de Petri temporel, graphe des classes.

KEYWORDS
preemptive system, DBM, polyhedral system, time Petri net, state class graph.

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  (465 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
Lavoisier