Complexity Analysis of Continuous Petri Nets

• Autorzy: Fraca E. , Haddad S.

Identyfikatory

DOI

10.3233/FI-2015-1168

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

continuous Petri nets; structural analysis; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 1
• Strony: 1--28
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Fraca E.

• Instituto de Investigación en Ingenier´ıa de Aragón (I3A) Universidad de Zaragoza, Zaragoza, Spain

autor

Haddad S.

• Ecole Normale Sup´erieure de Cachan, LSV, CNRS UMR 8643, INRIA, Cachan, France

Bibliografia

• [1] Avis, D., Fukuda, K., Picozzi, S.: On canonical representations of convex polyhedra, Mathematical Software, Proceedings of the First International Congress of Mathematical Software (A. M. Cohen, X.-S. Gao, N. Takayama, Eds.), World Scientific Publishing, 2002.
• [2] Bagnara, R., Hill, P. M., Zaffanella, E.: Not necessarily closed convex polyhedra and the double description method, Formal Aspects of Computing, 17(2), 2005, 222–257.
• [3] Cabasino, M. P., Seatzu, C., Mahulea, C., Silva, M.: Fault diagnosis of manufacturing systems using continuous Petri nets, Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Istanbul, Turkey, IEEE, 2010.
• [4] Codenotti, B., Leoncini, M., Preparata, F. P.: The Role of Arithmetic in Fast Parallel Matrix Inversion, Algorithmica, 30(4), 2001, 685–707.
• [5] David, R., Alla, H.: Continuous Petri Nets, Proc. of the 8th European Workshop on Application and Theory of Petri Nets, Zaragoza, Spain, 1987.
• [6] Desel, J., Esparza, J.: Free Choice Petri Nets, Cambridge Tracts in Theoretical Computer Science 40, 1995.
• [7] Desel, J., Neuendorf, K.-P., Radola, M.-D.: Proving Nonreachability by Modulo-Invariants, Theor. Comput. Sci., 153(1&2), 1996, 49–64.
• [8] Esparza, J., Nielsen, M.: Decidability Issues for Petri Nets - a survey, Elektronische Informationsverarbeitung und Kybernetik, 30(3), 1994, 143–160.
• [9] Gudiño-Mendoza, B., López-Mellado, E., Alla, H.: Modeling and simulation of water distribution systems using timed hybrid Petri nets, Simulation, 88(3), 2012, 329–347.
• [10] Júlvez, J., Recalde, L., Silva, M.: On reachability in autonomous continuous Petri net systems, 24th Int. Conf. on Application and Theory of Petri Nets (W. van der Aalst, E. Best, Eds.), 2679, Springer, Eindhoven, The Netherlands, 2003.
• [11] Júlvez, J., Recalde, L., Silva, M.: Steady state performance evaluation of continuous mono-T-semiflow Petri nets, Automatica, 41(4), May 2005, 605–616.
• [12] Papadimitriou, C. H.: Computational complexity, Addison-Wesley, 1994, ISBN 0201530821.
• [13] Papadimitriou, C. H., Steigliz, K.: Combinatorial Optimization. Algorithms and Complexity, Dover publications, second edition, 1998.
• [14] Recalde, L., Haddad, S., Silva, M.: Continuous Petri Nets: Expressive Power and Decidability Issues, Int. Journal of Foundations of Computer Science, 21(2), 2010, 235–256.
• [15] Recalde, L., Teruel, E., Silva, M.: Autonomous Continuous P/T systems, Application and Theory of Petri Nets 1999 (S. Donatelli, J. Kleijn, Eds.), 1639, Springer, Williamsburg, Virginia, USA, 1999.
• [16] Ross-Leon, R., Ramirez-Trevino, A., Morales, J. A., Ruiz-Leon, J.: Control of Metabolic Systems Modeled with Timed Continuous Petri Nets., ACSD/Petri Nets Workshops, 827, 2010.
• [17] Vázquez, C. R., Sutarto, H. Y., Boel, R. K., Silva, M.: Hybrid Petri Net Model of a Traffic Intersection in an Urban Network, Proceedings of the IEEE International Conference on Control Applications, CCA 2010, Yokohama, Japan, 2010.
• [18] Zerhouni, N., Alla, H.: Dynamic Analysis of Manufacturing Systems using Continuous Petri Nets., Proceedings of the IEEE International Conference on Robotics and Automation, 2, Cincinnati, OH, USA, 1990