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.
Type de document :
Article dans une revue
Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, Lavoisier, 2009, Numéro spécial "Réseaux de Petri", 28, pp.1171 - 1201
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

http://hal.univ-brest.fr/hal-01102905
Contributeur : Goulven Guillou <>
Soumis le : mardi 13 janvier 2015 - 16:32:34
Dernière modification le : vendredi 13 octobre 2017 - 01:12:47
Document(s) archivé(s) le : vendredi 11 septembre 2015 - 06:41:06

Fichier

tsirtsi.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01102905, version 1

Collections

Citation

Goulven Guillou. Group-nets et réseaux lexicographiques. Expressivité et décidabilité. Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, Lavoisier, 2009, Numéro spécial "Réseaux de Petri", 28, pp.1171 - 1201. 〈hal-01102905〉

Partager

Métriques

Consultations de la notice

201

Téléchargements de fichiers

97