PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

On Liveness and Reversibility of Equal-Conflict Petri Nets

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Konferencja
International Conference on Application and Theory of Petri Nets and Other Models of Concurrency (Petri Nets 2015), (36; 21–26.06.2015; Brussels, Belgium)
Języki publikacji
EN
Abstrakty
EN
Weighted Petri nets provide convenient models of many man-made systems. Real applications are often required to possess the fundamental Petri net properties of liveness and reversibility, as liveness preserves all the functionalities (fireability of all transitions) of the system and reversibility lets the system return to its initial state (marking) using only internal operations. Characterizations of both behavioral properties, liveness and reversibility, are known for wellformed weighted Choice-Free and ordinary Free-Choice Petri nets, which are special cases of Equal-Conflict Petri nets. However, reversibility is not well understood for this larger class, where choices must share equivalent preconditions, although characterizations of liveness are known. In this paper, we provide the first characterization of reversibility for all live Equal-Conflict Petri nets by extending, in a weaker form, a known condition that applies to the Choice-Free and Free-Choice subclasses. We deduce the monotonicity of reversibility in the live Equal-Conflict class. We also give counter-examples for other classes where the characterization does not hold. Finally, we focus on well-formed Equal-Conflict Petri nets, for which we offer the first polynomial sufficient conditions for liveness and reversibility, contrasting with the previous exponential time conditions.
Wydawca
Rocznik
Strony
83--119
Opis fizyczny
Bibliogr. 38 poz., rys.
Twórcy
autor
  • Department of Computing Science, Carl von Ossietzky, Universität Oldenburg, D-26111 Oldenburg, Germany
  • IBISC, Université d'Evry-Val-D'Essonne, 91025, Evry, France
  • LIP6, Sorbonne Universités, UPMC Paris 06, UMR 7606, F-75005, Paris, France
Bibliografia
  • [1] Esparza J, Nielsen M. Decidability issues for Petri nets–A survey. Bulletin of the EATCS. 1994;52:244–262.
  • [2] Lee EA, Messerschmitt DG. Synchronous Data Flow. Proceedings of the IEEE. 1987;75(9):1235–1245.
  • [3] Lee EA, Messerschmidt DG. Static scheduling of synchronous data flow programs for digital signal processing. In: IEEE Transaction on Computers. vol. 36; 1987. p. 24–35. Available from: http://dx.doi. org/10.1109/TC.1987.5009446. doi:10.1109/TC.1987.5009446.
  • [4] Sriram S, Bhattacharyya SS. Embedded multiprocessors: scheduling and synchronization. Signal Processing and Communications. CRC Press; 2009.
  • [5] Pino JL, Bhattacharyya SS, Lee EA. A hierarchical multiprocessor scheduling framework for synchronous dataflow graphs. University of California, Berkeley; 1995.
  • [6] Teruel E, Chrzastowski-Wachtel P, Colom JM, Silva M. On weighted T-systems. In: Jensen K, editor. Application and Theory of Petri Nets 1992. vol. 616 of Lecture Notes in Computer Science. Springer, Heidelberg; 1992. p. 348–367. Available from: http://dx.doi.org/10.1007/3-540-55676-1\_20. doi:10.1007/3-540-55676-1_20.
  • [7] Ezpeleta J, Colom JM, Martinez J. A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Robotics and Automation. 1995 Apr;11(2):173–184. Available from: http://dx.doi.org/10.1109/70.370500. doi:10.1109/70.370500.
  • [8] Teruel E, Colom JM, Silva M. Choice-Free Petri nets: a model for deterministic concurrent systems with bulk services and arrivals. IEEE Transactions on Systems, Man and Cybernetics, Part A. 1997;27(1):73–83. Available from: http://dx.doi.org/10.1109/3468.553226. doi:10.1109/3468.553226.
  • [9] Angeli D, Sontag ED. Graphs and the Dynamics of Biochemical Networks. In: Iglesias PA, Ingalls BP, editors. Control Theory and Systems Biology. The MIT Press; 2010. p. 125–142. Available from: http://dx.doi.org/10.7551/mitpress/9780262013345.001.0001. doi: 10.7551/mitpress/9780262013345. 001.0001.
  • [10] Araki T, Kasami T. Decidable problems on the strong connectivity of Petri net reachability sets. Theoretical Computer Science. 1977; 4(1):99–119. Available from: http://dx.doi.org/10.1016/0304-3975(77)90059-7. doi:10.1016/0304-3975(77)90059-7.
  • [11] de Frutos Escrig D, Johnen C. Decidability of Home Space Property. Univ. de Paris-Sud, Centre d’Orsay, LRI; 1989. LRI-503.
  • [12] Esparza J. Decidability and complexity of Petri net problems - an introduction. In: Reisig W, Rozenberg G, editors. Lectures on Petri Nets I: Basic Models. vol. 1491 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 1998. p. 374–428. Available from: http://dx.doi.org/10.1007/3-540-65306-6\_20. doi:10.1007/3-540-65306-6_20.
  • [13] Cheng A, Esparza J, Palsberg J. Complexity results for 1-safe nets. In: Shyamasundar R, editor. Foundations of Software Technology and Theoretical Computer Science. vol. 761 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 1993. p. 326–337. Available from: http://dx.doi.org/10.1016/0304-3975(94)00231-7. doi:10.1016/0304-3975(94)00231-7.
  • [14] Lipton R. The reachability problem requires exponential space. Department of Computer Science, Yale University; 1976. 62.
  • [15] Murata T. Petri nets : properties, analysis and applications. Proceedings of the IEEE. 1989 Apr;77(4):541–580. Available from: http://dx.doi.org/10.1109/5.24143. doi:10.1109/5.24143.
  • [16] Best E, Desel J, Esparza J. Traps characterize home states in free choice systems. Theoretical Computer Science. 1992;101(2):161–176. Available from: http://dx.doi.org/10.1016/0304-3975(92) 90048-K. doi:10.1016/0304-3975(92)90048-K.
  • [17] Desel J, Esparza J. Free Choice Petri Nets. vol. 40 of Cambridge Tracts in Theoretical Computer Science. New York, NY, USA: Cambridge University Press; 1995.
  • [18] Best E, Darondeau P. Petri Net Distributability. In: Clarke E, Virbitskaite I, Voronkov A, editors. Perspectives of Systems Informatics. vol. 7162 of Lecture Notes in Computer Science. Springer, Heidelberg; 2012. p. 1–18. Available from: http://dx.doi.org/10.1007/978-3-642-29709-0\_1. doi:10.1007/978-3-642-29709-0_1.
  • [19] Teruel E, Silva M. Structure theory of Equal Conflict systems. Theoretical Computer Science. 1996; 153(1&2):271–300. Available from: http://dx.doi.org/10.1016/0304-3975(95)00124-7. doi:10.1016/ 0304-3975(95)00124-7.
  • [20] Teruel E, Silva M. Liveness and home states in Equal Conflict systems. In: Marsan MA, editor. Application and Theory of Petri Nets 1993. vol. 691 of Lecture Notes in Computer Science. Springer, Heidelberg; 1993. p. 415–432. Available from: http://dx.doi.org/10.1007/3-540-56863-8\_59. doi:10.1007/3-540-56863-8_59.
  • [21] Barkaoui K, Couvreur JM, Klai K. On the Equivalence Between Liveness and Deadlock-Freeness in Petri Nets. In: Ciardo G, Darondeau P, editors. Applications and Theory of Petri Nets (ICATPN). vol. 3536 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2005. p. 90–107. Available from: http://dx.doi.org/10.1007/11494744\_7. doi:10.1007/11494744_7.
  • [22] Barkaoui K, Minoux M. A polynomial-time graph algorithm to decide liveness of some basic classes of bounded Petri nets. In: Jensen K, editor. Application and Theory of Petri Nets. Springer Berlin Heidelberg; 1992. p. 62–75. Available from: http://dx.doi.org/10.1007/3-540-55676-1\_4. doi:10.1007/3-540-55676-1_4.
  • [23] Recalde L, Teruel E, Silva M. On well-formedness analysis: the case of Deterministic Systems of Sequential Processes. In: Desel J, editor. Structures in Concurrency Theory. Workshops in Computing. Springer London; 1995. p. 279–293. Available from: http://dx.doi.org/10.1007/978-1-4471-3078-9\_19. doi:10.1007/978-1-4471-3078-9_19.
  • [24] Recalde L, Teruel E, Silva M. {SC}*ECS: a class of modular and hierarchical cooperating systems. In: Billington J, Reisig W, editors. Application and Theory of Petri Nets 1996. vol. 1091 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 1996. p. 440–459. Available from: http://dx.doi.org/10.1007/3-540-61363-3\_24. doi:10.1007/3-540-61363-3_24.
  • [25] Silva M, Teruel E, Colom JM. Linear algebraic and linear programming techniques for the analysis of place/transition net systems. In: Reisig W, Rozenberg G, editors. Lectures on Petri Nets I: Basic Models. vol. 1491 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 1998. p. 309–373. Available from: http://dx.doi.org/10.1007/3-540-65306-6\_19. doi:10.1007/3-540-65306-6_19.
  • [26] Esparza J, Silva M. A polynomial-time algorithm to decide liveness of bounded free choice nets. Theoretical Computer Science. 1992;102(1):185–205. Available from: http://dx.doi.org/10.1016/0304- 3975(92)90299-U. doi:10.1016/0304-3975(92)90299-U.
  • [27] Barkaoui K, Pradat-Peyre JF. On liveness and controlled siphons in Petri nets. In: Application and Theory of Petri Nets. Springer; 1996. p. 57–72. Available from: http://dx.doi.org/10.1007/3-540-61363-3\_4. doi:10.1007/3-540-61363-3_4.
  • [28] Hujsa T, Delosme JM, Munier-Kordon A. Polynomial Sufficient Conditions of Well-Behavedness and Home Markings in Subclasses of Weighted Petri nets. ACM Transactions on Embedded Computing Systems. 2014 July;13(4s):141:1–141:25. Available from: http://doi.acm.org/10.1145/2627349.doi:http://doi.acm.org/10.1145/2627349.
  • [29] Hujsa T, Delosme JM, Munier-Kordon A. On the Reversibility of Well-Behaved Weighted Choice-Free Systems. In: Ciardo G, Kindler E, editors. Application and Theory of Petri Nets and Concurrency. vol. 8489 of Lecture Notes in Computer Science. Springer International Publishing; 2014. p. 334–353. Available from: http://dx.doi.org/10.1007/978-3-319-07734-5\_18. doi:10.1007/978-3-319-07734-5_18.
  • [30] Marchetti O, Munier-Kordon A. A sufficient condition for the liveness of Weighted Event Graphs. European Journal of Operational Research. 2009;197(2):532–540. Available from: http://dx.doi.org/10.1016/j.ejor.2008.07.037. doi:10.1016/j.ejor.2008.07.037.
  • [31] Hujsa T, Delosme JM, Munier-Kordon A. On the Reversibility of Live Equal-Conflict Petri Nets. In: Devillers R, Valmari A, editors. Application and Theory of Petri Nets and Concurrency. vol. 9115 of Lecture Notes in Computer Science. Springer International Publishing; 2015. p. 234–253. Available from: http://dx.doi.org/10.1007/978-3-319-19488-2\_12. doi:10.1007/978-3-319-19488-2_12.
  • [32] Memmi G, Roucairol G. Linear algebra in net theory. In: Brauer W, editor. Net Theory and Applications. vol. 84 of Lecture Notes in Computer Science. Springer, Heidelberg; 1980. p. 213–223. Available from: http://dx.doi.org/10.1007/3-540-10001-6\_24. doi:10.1007/3-540-10001-6_24.
  • [33] Sifakis J. Structural properties of Petri nets. In: Winkowski J, editor. Mathematical Foundations of Computer Science. vol. 64 of Lecture Notes in Computer Science. Springer, Heidelberg; 1978. p. 474–483. Available from: http://dx.doi.org/10.1007/3-540-08921-7\_95. doi:10.1007/3-540-08921-7_95.
  • [34] Hack MHT. Analysis of production schemata by Petri nets. DTIC Document; 1972.
  • [35] Lopez-Grao JP, Colom JM. Structural Methods for the Control of Discrete Event Dynamic Systems – The case of the Resource Allocation Problem. In: Seatzu C, Silva M, van Schuppen JH, editors. Control of Discrete-Event Systems. vol. 433 of Lecture Notes in Control and Information Sciences. Springer London; 2013. p. 257–278. Available from: http://dx.doi.org/10.1007/978-1-4471-4276-8\_13. doi:10.1007/978-1-4471-4276-8_13.
  • [36] Recalde L, Teruel E, Silva M. Modeling and analysis of sequential processes that cooperate through buffers. IEEE Transactions on Robotics and Automation. 1998;14(2):267–277. Available from: http://dx.doi.org/10.1109/70.681245. doi:10.1109/70.681245.
  • [37] Desel J, Reisig W. Place/Transition Petri Nets. In: Reisig W, Rozenberg G, editors. Lectures on Petri Nets I: Basic Models. vol. 1491 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 1998. p. 122–173.
  • [38] Delosme JM, Hujsa T, Munier-Kordon A. Polynomial sufficient conditions of well-behavedness for weighted Join-Free and Choice-Free systems. In: Proceedings of the 13th International Conference on Application of Concurrency to System Design (ACSD’13); 2013. p. 90–99. Available from: http://dx.doi.org/10.1109/ACSD.2013.12. doi:10.1109/ACSD.2013.12.
Uwagi
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-bfc55632-3a02-4301-a60e-9d0608b0b0f7
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.