Complexity Analysis of Continuous Petri Nets
Fundamenta Informaticae · 2015-04 · 137 (1) · 1-28
DOI: 10.3233/fi-2015-1168 ↗Kurz gefasst
Fachartikel in der Zeitschrift Fundamenta Informaticae, 2015-04. Verfasst von Estíbaliz Fraca und 1 weiteren Autor:innen. Die Arbeit wurde bisher 22-mal zitiert (Crossref).
Abstract (Originalsprache)
At the end of the eighties, continuous Petri nets were introduced for: (1) alleviating the combinatory explosion triggered by discrete Petri nets (i.e. usual Petri nets) and, (2) modelling the behaviour of physical systems whose state is composed of continuous variables. Since then several works have established that the computational complexity of deciding some standard behavioural properties of Petri nets is reduced in this framework. Here we first establish the decidability of additional properties like coverability, boundedness and reachability set inclusion. We also design new decision procedures for reachability and lim-reachability problems with a better computational complexity. Finally we provide lower bounds characterising the exact complexity class of the reachability, the coverability, the boundedness, the deadlock freeness and the liveness problems. A small case study is introduced and analysed with these new procedures.
Zitieren
APA
Fraca, E., & Haddad, S. (2015). Complexity Analysis of Continuous Petri Nets. Fundamenta Informaticae, 137(1), 1-28. https://doi.org/10.3233/fi-2015-1168
Vancouver
Fraca E, Haddad S. Complexity Analysis of Continuous Petri Nets. Fundamenta Informaticae. 2015;137(1):1-28. doi:10.3233/fi-2015-1168
BibTeX
@article{Fraca2015,
author = {Fraca, Estíbaliz and Haddad, Serge},
title = {Complexity Analysis of Continuous Petri Nets},
journal = {Fundamenta Informaticae},
year = {2015},
volume = {137},
number = {1},
pages = {1--28},
doi = {10.3233/fi-2015-1168}
}
EUVIMED