Continuous Petri Nets: Expressive Power and Decidability Issues - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Foundations of Computer Science Année : 2010

Continuous Petri Nets: Expressive Power and Decidability Issues

Résumé

State explosion is a fundamental problem in the analysis and synthesis of discrete event systems. Continuous Petri nets can be seen as a relaxation of the corresponding discrete model. The expected gains are twofold: improvements in complexity and in decidability. In the case of autonomous nets we prove that liveness or deadlock-freeness remain decidable and can be checked more efficiently than in Petri nets. Then we introduce time in the model which now behaves as a dynamical system driven by differential equations and we study it w.r.t. expressiveness and decidability issues. On the one hand, we prove that this model is equivalent to timed differential Petri nets which are a slight extension of systems driven by linear differential equations (LDE). On the other hand, (contrary to the systems driven by LDEs) we show that continuous timed Petri nets are able to simulate Turing machines and thus that basic properties become undecidable.

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

hal-00779919 , version 1 (22-01-2013)

Identifiants

Citer

Laura Recalde, Serge Haddad, Manuel Silva. Continuous Petri Nets: Expressive Power and Decidability Issues. International Journal of Foundations of Computer Science, 2010, 21 (2), pp.235-256. ⟨10.1142/S0129054110007222⟩. ⟨hal-00779919⟩
123 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More