Combining Free Choice and Time in Petri Nets

Abstract : Time Petri nets (TPNs) (Merlin 1974) are a classical extension of Petri nets with timing constraints attached to transitions, for which most verification problems are undecidable. We consider TPNs under a strong semantics with multiple enabling of transitions. We focus on a structural subclass of unbounded TPNs, where the underlying untimed net is free choice, and show that it enjoys nice properties under a multi-server semantics. In particular, we show that the questions of fireability (whether a chosen transition can fire), and termination (whether the net has a non-terminating run) are decidable for this class. We then consider the problem of robustness under guard enlargement (Puri et al. 2000), i.e., whether a given property is preserved even if the system is implemented on an architecture with imprecise time measurement. This question was studied for TPNs in (Akshay et al. 2016), and decidability of several problems was obtained for bounded classes of nets. We show that robustness of fireability is decidable for unbounded free choice TPNs with a multi-server semantics.
Type de document :
Communication dans un congrès
IEEE. 23rd International Symposium on Temporal Representation and Reasoning , Oct 2016, Lyngby, Denmark. 2016, 23rd International Symposium on Temporal Representation and Reasoning 〈http://time2016.compute.dtu.dk/〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01379440
Contributeur : Loic Helouet <>
Soumis le : mardi 11 octobre 2016 - 15:08:26
Dernière modification le : mercredi 11 avril 2018 - 02:01:18
Document(s) archivé(s) le : samedi 4 février 2017 - 19:04:59

Fichier

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

Identifiants

  • HAL Id : hal-01379440, version 1

Citation

Sundararaman Akshay, Loïc Hélouët, Ramchandra Phawade. Combining Free Choice and Time in Petri Nets. IEEE. 23rd International Symposium on Temporal Representation and Reasoning , Oct 2016, Lyngby, Denmark. 2016, 23rd International Symposium on Temporal Representation and Reasoning 〈http://time2016.compute.dtu.dk/〉. 〈hal-01379440〉

Partager

Métriques

Consultations de la notice

312

Téléchargements de fichiers

48