On Deadlockability, Liveness and Reversibility in Subclasses of Weighted Petri Nets

• Autorzy: Hujsa T. , Devillers R.

Identyfikatory

DOI

10.3233/FI-2018-1708

• Konferencja: International Conference on Application and Theory of Petri Nets and Other Models of Concurrency (Petri Nets 2017) (31; School of Engineering and Architecture of Zaragoza University; 25.30.07.2017; Spain)
• Języki publikacji: EN

Abstrakty

EN

Liveness, (non-)deadlockability and reversibility are behavioral properties of Petri nets that are fundamental for many real-world systems. Such properties are often required to be monotonic, meaning preserved upon any increase of the marking. However, their checking is intractable in general and their monotonicity is not always satisfied. To simplify the analysis of these features, structural approaches have been fruitfully exploited in particular subclasses of Petri nets, deriving the behavior from the underlying graph and the initial marking only, often in polynomial time. In this paper, we further develop these efficient structural methods to analyze deadlockability, liveness, reversibility and their monotonicity in weighted Petri nets. We focus on the join-free subclass, which forbids synchronizations, and on the homogeneous asymmetric-choice subclass, which allows conflicts and synchronizations in a restricted fashion. For the join-free nets, we provide several structural conditions for checking liveness, (non-)deadlockability, reversibility and their monotonicity. Some of these methods operate in polynomial time. Furthermore, in this class, we show that liveness, non-deadlockability and reversibility, taken together or separately, are not always monotonic, even under the assumptions of structural boundedness and structural liveness. These facts delineate more sharply the frontier between monotonicity and non-monotonicity of the behavior in weighted Petri nets, present already in the join-free subclass. In addition, we use part of this new material to correct a flaw in the proof of a previous characterization of monotonic liveness and boundedness for homogeneous asymmetric-choice nets, published in 2004 and left unnoticed.

Słowa kluczowe

EN

structural analysis; weighted Petri net; deadlockability; liveness; reversibility; boundedness; monotonicity; fork-attribution; join-free; communication-free; synchronization-free; asymmetric-choice

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 161, nr 4
• Strony: 383--421
• Opis fizyczny: Bibliogr. 31 poz., rys., tab.

Twórcy

autor

Hujsa T.

• Department of Computing Science, Carl von Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany

autor

Devillers R.

• Département d’Informatique, Université Libre de Bruxelles, Brussels, Belgium

Bibliografia

• [1] Lee EA, Messerschmitt DG. Synchronous Data Flow. Proceedings of the IEEE, 1987. 75(9):1235-1245. doi:10.1109/PROC.1987.13876.
• [2] 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. doi:10.1109/3468.553226.
• [3] Esparza J, Nielsen M. Decidability issues for Petri nets-A survey. BRICS Report Series, 1994. 1(8). doi:10.1.1.2.3965.
• [4] Araki T, Kasami T. Decidable problems on the strong connectivity of Petri net reachability sets. Theoretical Computer Science, 1977. 4(1):99-119. doi:10.1016/0304-3975(77)90059-7.
• [5] de Frutos Escrig D, Johnen C. Decidability of Home Space Property. Technical Report LRI-503, Univ. de Paris-Sud, Centre d’Orsay, LRI, 1989.
• [6] Esparza J. Decidability and complexity of Petri net problems-an introduction. In: Reisig W, Rozenberg G (eds.), Lectures on Petri Nets I: Basic Models, volume 1491 of LNCS. 1998 pp. 374-428. doi:10.1007/3-540-65306-6\_20.
• [7] Cheng A, Esparza J, Palsberg J. Complexity results for 1-safe nets. In: Shyamasundar R (ed.), Foundations of Software Technology and Theoretical Computer Science, volume 761 of LNCS. 1993 pp. 326-337. doi:10.1007/3-540-57529-4\_66.
• [8] Lipton R. The reachability problem requires exponential space. Technical Report 62, Department of Computer Science, Yale University, 1976.
• [9] Teruel E, Silva M. Structure theory of Equal Conflict systems. Theoretical Computer Science, 1996. 153(1&2):271-300. doi:10.1016/0304-3975(95)00124-7.
• [10] Jiao L, Cheung TY, Lu W. On liveness and boundedness of Asymmetric Choice nets. Theoretical Computer Science, 2004. 311(1-3):165-197. doi:10.1016/S0304-3975(03)00359-1.
• [11] Hujsa T, Delosme JM, Munier-Kordon A. On Liveness and Reversibility of Equal-Conflict Petri Nets. Fundamenta Informaticae, 2016. 146(1):83-119. doi:10.3233/FI-2016-1376.
• [12] Barkaoui K, Minoux M. A polynomial-time graph algorithm to decide liveness of some basic classes of bounded Petri nets. In: Jensen K (ed.), Application and Theory of Petri Nets, volume 616 of LNCS. 1992 pp. 62-75. doi:10.1007/3-540-55676-1\_4.
• [13] Desel J, Esparza J. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, New York, USA, 1995. doi:10.1017/CBO9780511526558.
• [14] 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 (eds.), Lectures on Petri Nets I: Basic Models, volume 1491 of LNCS. 1998 pp. 309-373. doi:10.1007/3-540-65306-6\_19.
• [15] 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. doi:10.1109/70.681245.
• [16] Barkaoui K, Couvreur JM, Klai K. On the Equivalence Between Liveness and Deadlock-Freeness in Petri Nets. In: Ciardo G, Darondeau P (eds.), Applications and Theory of Petri Nets, volume 3536 of LNCS. 2005 pp. 90-107. doi:10.1007/11494744\_7.
• [17] Hujsa T, Delosme JM, Munier-Kordon A. Polynomial Sufficient Conditions of Well-Behavedness and Home Markings in Subclasses of Weighted Petri nets. Transactions on Embedded Computing Systems, 2014. 13(4s):141:1-141:25. doi:10.1145/2627349.
• [18] Hujsa T, Delosme JM, Munier-Kordon A. On the Reversibility of Well-Behaved Weighted Choice-Free Systems. In: Ciardo G, Kindler E (eds.), Application and Theory of Petri Nets and Concurrency, volume 8489 of Lecture Notes in Computer Science, pp. 334-353. Springer International Publishing, 2014. doi:10.1007/978-3-319-07734-5\_18.
• [19] Heiner M, Mahulea C, Silva M. On the Importance of the Deadlock Trap Property for Monotonic Liveness. In: International Workshop on Biological Processes and Petri nets (BioPPN), A satellite event of Petri Nets 2010. 2010 pp. 23-38.
• [20] Barkaoui K, Pradat-Peyre JF. On liveness and controlled siphons in Petri nets. In: Billington J, Reisig W (eds.), Application and Theory of Petri Nets, volume 1091 of LNCS. 1996 pp. 57-72. doi:10.1007/3-540-61363-3\_4.
• [21] Hujsa T, Delosme JM, Munier-Kordon A. Application and Theory of Petri Nets and Concurrency: 36th International Conference, Petri nets 2015, Brussels, Belgium, June 21-26, 2015, Proceedings, chapter On the Reversibility of Live Equal-Conflict Petri Nets, pp. 234-253. Springer International Publishing, 2015. doi:10.1007/978-3-319-19488-2\_12.
• [22] Hujsa T, Devillers R. On Liveness and Deadlockability in Subclasses of Weighted Petri Nets. In: van der Aalst W, Best E (eds.), Application and Theory of Petri Nets and Concurrency: 38th International Conference, PETRI NETS 2017, Zaragoza, Spain, June 25-30, 2017, Proceedings. Springer International Publishing, Cham. ISBN 978-3-319-57861-3, 2017 pp. 267-287. doi:10.1007/978-3-319-57861-3\_16.
• [23] Recalde L, Teruel E, Silva M. {SC}*ECS: A class of modular and hierarchical cooperating systems. In: Billington J, Reisig W (eds.), Application and Theory of Petri Nets 1996. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-540-68505-0, 1996 pp. 440-459. doi:10.1007/3-540-61363-3\_24.
• [24] Mayr EW, Weihmann J. Results on Equivalence, Boundedness, Liveness, and Covering Problems of BPP-Petri Nets. In: Application and Theory of Petri Nets and Concurrency. 2013 pp. 70-89. doi:10.1007/978-3-642-38697-8\_5.
• [25] Mayr EW, Weihmann J. Complexity results for problems of communication-free Petri nets and related formalisms. Fundamenta Informaticae, 2015. 137(1):61-86. doi:10.3233/FI-2015-1170.
• [26] Teruel E, Silva M. Liveness and home states in Equal Conflict systems. In: Marsan MA (ed.), Application and Theory of Petri Nets 1993, volume 691 of LNCS. 1993 pp. 415-432. doi:10.1007/3-540-56863-8\_59.
• [27] Teruel E. Structure Theory of Weighted Place/Transition Net Systems: The Equal Conflict Hiatus. thesis, DIEI. University of Zaragoza, Spain, 1994.
• [28] Sifakis J. Structural properties of Petri nets. In: Winkowski J (ed.), Mathematical Foundations of Computer Science, volume 64 of LNCS. 1978 pp. 474-483. doi:10.1007/3-540-08921-7\_95.
• [29] Grötschel M, Lovász L, Schrijver A. Geometric algorithms and combinatorial optimization. Algorithms and combinatorics. Springer-Verlag, 1993. ISBN 9780387136240. doi:10.1007/978-3-642-78240-4.
• [30] Delosme J, Hujsa T, Kordon AM. Polynomial Sufficient Conditions of Well-Behavedness for Weighted Join-Free and Choice-Free Systems. In: 13th International Conference on Application of Concurrency to System Design, ACSD 2013, Barcelona, Spain, 8-10 July, 2013. 2013 pp. 90-99. doi:10.1109/ACSD.2013.12.
• [31] Teruel E, Chrzastowski-Wachtel P, Colom JM, Silva M. On weighted T-systems. In: Jensen K (ed.), Application and Theory of Petri Nets 1992, volume 616 of LNCS, pp. 348-367. Springer, Heidelberg, 1992. doi:10.1007/3-540-55676-1\_20.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).