La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets Décidabilité temporelle polynomiale de la vivacité monotone des réseaux AC/DC limités dans le temps

Atsushi OHTA, Kohkichi TSUJI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le réseau de Petri est un modèle mathématique pour les systèmes concurrents. La vivacité est l’une des propriétés importantes du réseau de Petri. Le problème de vivacité du réseau de Petri général est d'une complexité spatiale exponentielle et les sous-classes sont suggérées avec moins de complexité informatique. Il est bien connu que le problème de vivacité d’un réseau de libre choix limité (étendu) est résolu en temps polynomial déterministe. Cet article traite du problème de vivacité des réseaux AC/DC. AC/DC net est une sous-classe du réseau Petri qui ne présente aucune confusion (mélange de concurrence et de conflit). Cette classe inclut à juste titre la classe des moustiquaires à libre choix. Il est montré que tout siphon minimal d’un réseau AC/DC est un piège si et seulement si tout siphon fortement connecté est un piège. Ce résultat montre que la vivacité monotone du réseau AC/DC borné est résolue en temps polynomial déterministe. Il est montré que ce résultat est vrai pour un temps limité AC/DC net avec des conditions statiques acceptables.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.11 pp.2865-2870
Date de publication
2001/11/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Concurrent Systems Technology)
Catégories

Auteurs

Mots-clés

Table des matières