An Axiomatization of the Token Game Based on Petri Algebras

• Autorzy: Badouel E. , Chenou J. , Guillou G.
• Języki publikacji: EN

Abstrakty

EN

The firing rule of Petri nets relies on a residuation operation for the commutative monoid of non negative integers. We identify a class of residuated commutative monoids, called Petri algebras, for which one can mimic the token game of Petri nets to define the behaviour of generalized Petri nets whose flow relations and place contents are valued in such algebraic structures. The sum and its associated residuation capture respectively how resources within places are produced and consumed through the firing of a transition. We show that Petri algebras coincide with the positive cones of lattice-ordered commutative groups and constitute the subvariety of the (duals of) residuated lattices generated by the commutative monoid of non negative integers. We however exhibit a Petri algebra whose corresponding class of nets is strictly more expressive than the class of Petri nets. More precisely, we introduce a class of nets, termed lexicographic Petri nets, that are associated with the positive cones of the lexicographic powers of the additive group of real numbers. This class of nets is universal in the sense that any net associated with some Petri algebra can be simulated by a lexicographic Petri net. All the classical decidable properties of Petri nets however (termination, covering, boundedness, structural boundedness, accessibility, deadlock, liveness ...) are undecidable on the class of lexicographic Petri nets. Finally we turn our attention to bounded nets associated with Petri algebras and show that their dynamics can be reformulated in term of MV-algebras.

Słowa kluczowe

EN

Petri net; axiomatization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 77, nr 3
• Strony: 187--215
• Opis fizyczny: bibliogr. 34 poz.

Twórcy

autor

Badouel E.

autor

Chenou J.

autor

Guillou G.

• INRIA, Irisa, Campus de Beaulieu, F35042 Rennes Cedex, France,

Bibliografia

• [1] Badouel, E., Darondeau, Ph.: Dualities between nets and automata induced by schizophrenic objects. Proc. 6th International Conference on Category Theory and Computer Science, Lecture Notes in Computer Science vol. 953, Springer-Verlag, Berlin, 1995, 24-43.
• [2] Badouel, E., Darondeau, Ph.: Theory of Regions. Advance Course on Petri Nets, Dagstuhl Castle, W. Reisig and G. Rozenberg, editors. Lectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science vol. 1491, Springer-Verlag, Berlin, 1995, 529-586.
• [3] Badouel, E., Chenou, J.: Nets Enriched over Closed Monoidal Structures, Proc. ICATPN'03, Eindhoven, Lecture Notes in Computer Science vol. 2679, Springer-Verlag, Berlin, 2003, 64-81.
• [4] Bahls, P., Cole, J., Galatos, N., Jipsen, P., Tsinakis, C.: Cancellative residuated lattices. Algebra Universalis 50(1), 2003, 83-106.
• [5] Birkhoff, G.: Lattice Theory. Third edition, AMS Colloquium Publications, vol. XXV (American Mathematical Society, Providence, 1967).
• [6] Blount, K.: On the structure of residuated lattices. Ph. D. Thesis, Dept. of Mathematics, (Vanderbilt University, Nashville, Tennessee, 1999).
• [7] Blount, K., Tsinakis, C.: The structure of Residuated Lattices. International Journal of Algebra and Computation 13(4), 2003, 437-461.
• [8] Braun, P., Brosowski, B., Fisher, T., Helbig, S.: A group-theoretical Approach to General Petri Nets. Technical report, University of Frankfurt, 1991.
• [9] Brown, C.: Relating Petri Nets to Formulae of Linear Logic. Technical Report ECS LFCS 89-87, University of Edinburgh, 1989.
• [10] Brown, C., Gurr, D.: A categorical linear framework from Petri nets. Information and Computation, 122(2), 1995, 268-285.
• [11] Cardoso, J., Camargo, H., Eds.: Fuzziness in Petri Nets, Physica Verlag, New-York, N.Y., 1999.
• [12] Cardoso, J., Valette, R., Dubois,D.: Fuzzy Petri nets: An overview, Proc. 13rd IFAC World Congress, San Francisco, California (G. Rozenberg, Ed.), 1996, 443-448.
• [13] Cardoso, J., Valette, R., Dubois, D.: Possibilistic Petri nets. IEEE Transactions on Systems, Man and Cybernetics, Part B: Cybernetics, October 1999, 29(5), 573-582.
• [14] Cignoli, R., D'Ottaviano, I., Mundici, D.: Algebraic foundations of many-valued reasoning, Trends in Logicstudia Logica Library 7, Kluwer Academic Publishers, Dordrecht, 2000.
• [15] David, R., Alla, H.: Petri nets for modeling of dynamic systems - a survey. Automatica, 30, 1994, 175-202.
• [16] Droste, M., Shortt, R.M.: Continuous Petri nets and transition systems, Uniform approaches to Petri nets, Advances in Petri nets (H. Ehrig, J. Padberg, G. Rozenberg, Eds.), Lecture Notes in Computer Science vol. 2128, Springer-Verlag, Berlin, 2001, 457-484.
• [17] Engberg, U.,Winskel, G.: Petri nets as models of linear logic. Proceedings of Colloquium on Tree in Algebra and Programming, Copenhagen, Denmark (A. Arnold, Ed.), Lecture Notes in Computer Science vol. 389, Springer-Verlag, Berlin, 1990, 147-161.
• [18] Engberg, U., Winskel, G.: Completness result for linear logic on Petri nets. Annals of Pure and Applied Logic, 86(2), 1997, 101-135.
• [19] Engeler. E.: Foundations of Mathematics: Questions of Analysis, Geometry and Algorithmics. Springer-Verlag, 1993.
• [20] Fuchs, L.: Partially ordered algebraic systems, Pergamon Press, 1963.
• [21] Galatos, N.: Varieties of Residuated Lattices. Ph. D. Thesis, Dept. of Mathematics, Vanderbilt University, Nashville, Tennessee, 2003.
• [22] Gehlot, V., Gunter, C. A.: Nets as tensor theories. proc. of the tenth International Conference on Application and theory of Petri Nets (G. De Michelis, Ed.), Bonn, Germany, 1989, 174-191.
• [23] Girard, J.-Y.: Linear logic. Theoretical Computer Science 50, 1987, 1-102.
• [24] Jipsen, P., Tsinakis, C.: A survey of Residuated Lattices, Ordered Algebraic Structures (J. Martinez, Ed.), Kluwer Academic Publishers, Dordrecht, 2002, 19-56.
• [25] Juhás, G., The essence of Petri nets and transition systems through abelian groups, Electronic Notes in Theoretical Computer Science 18 1998.
• [26] Juhás, G., Petri nets with generalized algebras: a comparison, Electronic Notes in Theoretical Computer Science 27, 1999.
• [27] Memmi, G., Finkel, A.: An introduction to fifo nets - monogeneous nets: a subclass of fifo nets. Theoretical Computer Science 35, 1985, 191-214.
• [28] Martí-Oliet, N., Meseguer, J.: From Petri nets to linear logic, Mathematical Structures in Computer Science 1(1), 1991, 69-101.
• [29] Martí-Oliet, N., Meseguer, J.: From Petri nets to linear logic through categories: A survey, Journal on Foundations of Computer Science, 2(4), 1991, 297-399.
• [30] Meseguer, J., Montanari, U.: Petri Nets are Monoids, Information and Computation, 88(2), 1990, 105-155.
• [31] Mundici, D.: Interpretation of AF C*-algebras in Lukasiewicz sentential calculus, Journal of Functional Analysis 65(1), 1986, 15-63.
• [32] Retoré, C.: A representation of the non-sequential execution of Petri nets in Partially commutative linear logic, Proc. of the Annual European Summer Meeting of the Association for Symbolic Logic (J. Van Eijck, V. Van Oostrom, A. Visser, Eds.), Utrecht, The Netherlands, Lecture Notes in Logic 17 (1999).
• [33] Rosenthal, K. I.: A note on Girard Quantales, Cahier de géométrie différentielle catégorique 31, 1990, 1-11.
• [34] Silva, M., Teruel, E., Colom, J.M.: Linear Algebraic and Linear Programming Techniques for the Analysis of Place/Transition Net Systems, Third Advance Course on Petri Nets, Dagstuhl Castle (W. Reisig and G. Rozenberg, Eds.), Lectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science vol 1491, 1995, 309-373.