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.1171-1201  - doi:10.3166/tsi.28.1171-1201
TITRE
Group-nets et réseaux lexicographiques. Expressivité et décidabilité

RÉSUMÉ
Les motivations liées aux extensions algébriques des réseaux de Petri portent entre autres sur des problèmes de modélisation, de vision unifiée ou abstraite des grandes classes de réseaux de Petri et d'obtention de modèles plus expressifs limitant les pertes du point de vue de la décidabilité. Nous proposons deux grandes classes de réseaux, les group ­ nets et les réseaux lexicographiques, la première se déclinant elle-même en plusieurs sous-classes. Nous étudions les liens entre ces réseaux et différentes classes usuelles de réseaux de Petri en donnant, dans le cas d'inclusions, les algorithmes permettant de passer de l'un à l'autre. Des outils sont donnés pour résoudre certains problèmes de décidabilité pour les strict- Z -nets et les Z -nets. On montre, en revanche, que les réseaux lexicographiques ont la puissance des machines de Turing rendant tout problème non trivial les concernant indécidable.


ABSTRACT
Algebraically generalized Petri nets are motivated by, among others, problems of modelling, the need to obtain an abstract and general frame of the most part of the common classes of Petri nets and the wish to obtain more expressive models which restrict loss at the level of the decidability. We propose two classes of nets, group - nets and lexicographic nets, the former containing itself several subclasses. We study the links between these nets and various classes of usual Petri nets. In the case of inclusions, we exhibit the algorithms which allow to pass from a class to the other one. Tools are given to resolve some decidability problems for strict- Z -nets and Z -nets. We show that lexicographic nets are Turing powerful, therefore all non-trivial problems are undecidable on this class.


AUTEUR(S)
G. GUILLOU

MOTS-CLÉS
extensions algébriques des réseaux de Petri, expressivité, décidabilité.

KEYWORDS
algebraically generalised Petri nets, expressiveness, decidability.

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



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
Lavoisier