Synthesis of Live and Bounded Persistent Systems

• Autorzy: Best E. , Devillers R.

Identyfikatory

DOI

10.3233/FI-2015-1244

• Języki publikacji: EN

Abstrakty

EN

This paper presents a dedicated Petri net synthesis algorithm for the case that a transition system is finite, live, and persistent. In particular, the paper delineates exactly when and how a structurally persistent net may be constructed, by crystallising, out of a general region-theoretic approach, a minimised set of simplified systems of linear inequalities. This extends previous results where reversibility, instead of liveness, played an important role.

Słowa kluczowe

EN

cyclic behavior; persistence; labelled transition systems; liveness; parikh vectors; Petri nets; region theory; system synthesis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 140, nr 1
• Strony: 39--59
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Best E.

• Parallel Systems, Department of Computing Science Carl von Ossietzky Universit¨at Oldenburg D-26111 Oldenburg, Germany

autor

Devillers R.

• Département d’Informatique Université Libre de Bruxelles Boulevard du Triomphe - C.P. 212, B-1050 Bruxelles, Belgium

Bibliografia

• [1] É. Badouel, L. Bernardinello, P. Darondeau: Polynomial Algorithms for the Synthesis of Bounded Nets. P.D. Mosses, M. Nielsen, M.I. Schwartzbach (eds): Proc. TAPSOFT’95, Aarhus, LNCS Vol. 915, pp. 364–378 (1995).
• [2] ´ E. Badouel, P. Darondeau: Theory of Regions. In W. Reisig, G. Rozenberg (eds): Lectures on Petri Nets I: Basic Models. LNCS Vol. 1491, pp. 529–586 (1998).
• [3] E. Best, P. Darondeau: A Decomposition Theorem for Finite Persistent Transition Systems. Acta Informatica 46:237–254 (2009).
• [4] E. Best, P. Darondeau: Petri Net Distributability. I. Virbitskaite, A. Voronkov (eds): Proc. PSI’11, Novosibirsk, LNCS Vol. 7162, pp. 1–18 (2011).
• [5] E. Best, R. Devillers: A Characterisation of the State Spaces of Live and Bounded Marked Graph Petri Nets. A.-H. Dediu, C. Mart´ın-Vide, J.-L. Sierra-Rodr´ıguez, B. Truthe (eds): Proc. LATA’14, Madrid, LNCS Vol. 8370, pp. 161–172 (2014).
• [6] E. Best, R. Devillers: Synthesis of Persistent Systems. In G. Ciardo, E. Kindler (eds): Proc. ICATPN’14, Tunis, LNCS Vol. 8489, pp. 111-129 (2014).
• [7] E. Best, R. Devillers: Synthesis and Reengineering of Persistent Systems. R. van Glabbeek, U. Goltz, E.-R. Olderog (eds): Special volume on the occasion of the 25’th anniversary of Combining Compositionality and Concurrency workshops. Acta Informatica, Vol. 52(1), pp. 35-60 (February 2015).
• [8] E. Best, R. Devillers: State Space Axioms for T-Systems. G. L¨uttgen, F. Corradini (eds): Special volume on the occasion of Walter Vogler’s 60th birthday. Acta Informatica, Vol. 52(2-3), pp. 133-152 (April 2015).
• [9] J. Carmona, J. Cortadella, V. Khomenko, A. Yakovlev: Synthesis of Asynchronous Hardware from Petri Nets. In: Lectures on Concurrency and Petri Nets. J. Desel,W. Reisig, G. Rozenberg (eds). Advances in Petri Nets, LNCS Vol. 3098, pp. 345-401 (2004).
• [10] F. Commoner, A.W. Holt, S. Even, A. Pnueli: Marked Directed Graphs. J. Comput. Syst. Sci. 5(5): 511-523 (1971).
• [11] S. Crespi-Reghizzi, D. Mandrioli: A Decidability Theorem for a Class of Vector Addition Systems. Information Processing Letters 3, 78–80 (1975).
• [12] M. Hack : Analysis of Production Schemata by Petri Nets, M.S. Thesis, D.E.E. MIT. Cambridge Mass. Project MAC-TR 94, 1972.
• [13] J. Júlvez, L. Recalde, M. Silva: Deadlock-Freeness Analysis of Continuous Mono-T-Semiflow Petri Nets IEEE Transactions on Automatic Control, Vol. 51- 9, pp. 1472-1481 (2006).
• [14] R.M. Keller: A Fundamental Theorem of Asynchronous Parallel Computation. Parallel Processing, LNCS Vol. 24, pp. 102–112 (1975).
• [15] A. Kondratyev, J. Cortadella, M. Kishinevsky, E. Pastor, O. Roig, A. Yakovlev: Checking Signal Transition Graph Implementability by Symbolic BDD Traversal. Proc. EDTC’95, Paris, pp. 325–332 (1995).
• [16] Leslie Lamport: Arbiter-Free Synchronization. Distributed Computing 16, 2/3, pp. 219-237 (2003).
• [17] L.H. Landweber, E.L. Robertson: Properties of Conflict-Free and Persistent Petri Nets. JACM 25(3), pp. 352–364 (1978).
• [18] G. Memmi, G. Roucairol: Linear Algebra in Net Theory. W. Brauer (ed.): Net Theory and Applications. LNCS Vol. 84, pp. 213–223 (1979).
• [19] L. Recalde, M. Silva, J. Ezpeleta, E. Teruel: Petri Nets and Manufacturing Systems: an examples-driven tour. In: Lectures on Concurrency and Petri Nets. J. Desel,W. Reisig, G. Rozenberg (eds). Advances in Petri Nets, LNCS Vol. 3098, pp. 742-788 (2004).
• [20] E. Teruel, J.M. Colom, M. Silva: Choice-Free Petri Nets: a model for deterministic concurrent systems with bulk services and arrivals. IEEE Transactions on Systems, Man and Cybernetics (Part A), Vol. 27-1, pp. 73-83 (1997).
• [21] A. Yakovlev: Designing Control Logic for Counterflow Pipeline Processor Using Petri Nets. Formal Methods in Systems Design, Vol. 12-1, Kluwer, pp. 39-71 (1998).