A Survey of Decidability Results for Elementary Object Systems

• Autorzy: Köhler-Bußmeier M.
• Języki publikacji: EN

Abstrakty

EN

This contribution presents recent results on Elementary Object Systems (EOS). Object nets are Petri nets which have Petri nets as tokens – an approach known as the nets-within-nets paradigm. In this work we study the relationship of EOS to existing Petri net formalisms. It turns out that EOS are equivalent to counter programs. But even for the restricted subclass of conservative EOS reachability and liveness are undecidable problems. On the other hand for other properties like boundedness are still decidable for conservative EOS. We also study the sub-class of generalised state machines, which is worth mentioning since it combines decidability of many theoretically interesting properties with a quite rich practical modelling expressiveness.

Słowa kluczowe

EN

Petri nets; nets within nets; reachability; liveness; boundedness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 1
• Strony: 99--123
• Opis fizyczny: Bibliogr. 45 poz., rys.

Twórcy

autor

Köhler-Bußmeier M.

• University of Hamburg, Department for Informatics Vogt-K¨olln-Straße 30, D-22527 Hamburg, Germany

Bibliografia

• [1] Abdulla, P. A., Cerans, K., Jonsson, B., Tsay, Y. K.: General Decidability Theorems for Infinite-State Systems, 11th Annual IEEE Symposium on Logic in Computer Science, LICS, 1996.
• [2] Bednarczyk,M. A., Bernardinello, L., Pawlowski,W., Pomello, L.: Modelling mobility with Petri hypernets, Recent Trends in Algebraic Development Techniques (J. L. Fiadeiro et al., Eds.), 3423, Springer, 2004.
• [3] Bonnet, R., Finkel, A., Leroux, J., Zeitoun,M.: Model Checking Vector Addition Systems with one zero-test, Logical Methods in Computer Science, 8(2), June 2012, 11.
• [4] Cardelli, L., Gordon, A. D., Ghelli, G.: Mobility types for mobile ambients, Proceedings of the Conference on Automata, Languages, and Programming (ICALP’99), 1644, Springer-Verlag, 1999.
• [5] Dufourd, C., Finkel, A., Schnoebelen, P.: Reset nets between decidability and undecidability, Automata, Languages, and Programming (ICALP’98) (K. Larsen, Ed.), 1443, Springer-Verlag, 1998.
• [6] Esparza, J.: Decidability and Complexity of Petri Net Problems – An Introduction, Lectures on Petri Nets I: Basic Models, Advances in Petri Nets (W. Reisig, G. Rozenberg, Eds.), 1491, Springer-Verlag, 1998.
• [7] Farwer, B.: A Linear Logic View of Object Petri Nets, Fundamenta Informaticae, 37(3), 1999, 225–246.
• [8] Finkel, A., Schnoebelen, P.: Well-structured Transition systems everywhere!, Theoretical Computer Science, 256(1-2), 2001, 63–92.
• [9] Haddad, S., Poitrenaud, D.: Theoretical Aspects of Recursive Petri Nets, Application and Theory of Petri Nets (S. Donatelli, J. Kleijn, Eds.), 1639, Springer-Verlag, 1999.
• [10] Hiraishi, K.: PN2: An Elementary Model for Design and Analysis of Multi-agent Systems, Coordination Models and Languages, COORDINATION 2002 (F. Arbab, C. L. Talcott, Eds.), 2315, Springer-Verlag, 2002.
• [11] Hoffmann, K., Ehrig, H., Mossakowski, T.: High-Level Nets with Nets and Rules as Tokens, Application and Theory of Petri Nets and Other Models of Concurrency, 3536, Springer-Verlag, 2005.
• [12] Jantzen, M., Valk, R.: Formal Properties of Place/Transition Nets, Net Theory and Applications (W. Brauer, Ed.), 84, Springer-Verlag, 1980.
• [13] Jones, N. D., Landweber, L. H., Lien, Y. E.: Complexity of Some Problems in Petri Nets, Theoretical Computer Science, 4, 1977, 277–299.
• [14] Karp, R.M., Miller, R. E.: Parallel Program Schemata, Journal of Computer and System Sciences, 3(2),May 1969, 147–195.
• [15] Köhler, M.: Reachable Markings of Object Petri Nets, Fundamenta Informaticae, 79(3-4), 2007, 401 – 413.
• [16] Köhler, M., Moldt, D., Rölke, H.: Modelling Mobility and Mobile Agents using Nets within Nets, Application and Theory of Petri Nets 2003 (W. v. d. Aalst, E. Best, Eds.), 2679, Springer-Verlag, 2003.
• [17] Köhler, M., Rölke, H.: Concurrency for Mobile Object-Net Systems, Fundamenta Informaticae, 54(2-3), 2003.
• [18] Köhler, M., Rölke, H.: Properties of Object Petri Nets, Application and Theory of Petri Nets 2004 (J. Cortadella, W. Reisig, Eds.), 3099, Springer-Verlag, 2004.
• [19] Köhler, M., Rölke, H.: Reference and Value Semantics are equivalent for Ordinary Object Petri Nets, Application and Theory of Petri Nets 2005 (P. Darondeau, G. Ciardo, Eds.), 3536, Springer-Verlag, 2005.
• [20] Köhler-Bußmeier, M.: Hornets: Nets within Nets combined with Net Algebra, Application and Theory of Petri Nets 2009 (K. Wolf, G. Franceschinis, Eds.), 5606, Springer-Verlag, 2009.
• [21] Köhler-Bußmeier, M.: A Survey of Elementary Object Systems: Decidability Results, Technical report, University of Hamburg 2011,
• [22] Köhler-Bußmeier, M., Heitmann, F.: On the Expressiveness of Communication Channels for Object Nets, Fundamenta Informaticae, 93(1-3), 2009, 205–219.
• [23] Köhler-Bußmeier, M., Heitmann, F.: Safeness for Object Nets, Fundamenta Informaticae, 101(1-2), 2010, 29–43.
• [24] Köhler-Bußmeier,M., Heitmann, F.: Liveness of Safe Object Nets, Fundamenta Informaticae, 112(1), 2011, 73–87.
• [25] Kummer, O.: Undecidability in Object-Oriented Petri Nets, Petri Net Newsletter, 59, 2000, 18–23.
• [26] Kummer, O.: Referenznetze, Logos Verlag, 2002.
• [27] Kummer, O., Wienberg, F., Duvigneau,M. et al. An Extensible Editor and Simulation Engine for Petri Nets: Renew, Application and Theory of Petri Nets 2004 (J. Cortadella, W. Reisig, Eds.), 3099, Springer-Verlag, 2004.
• [28] Lakos, C.: A Petri Net View ofMobility, Formal Techniques for Networked and Distributed Systems (FORTE 2005), 3731, Springer-Verlag, 2005.
• [29] Lambert, J.-L.: A structure to decide the reachability in Petri nets, Theoretical Computer Science, 99, 1992, 79–104.
• [30] Lomazova, I. A.: Nested Petri Nets – a Formalism for Specification of Multi-agent distributed systems, Fundamenta Informaticae, 43(1-4), 2000, 195–214.
• [31] Lomazova, I.: Nested Petri Nets for Adaptive Process Modeling, in: Pillars of Computer Science (A. Avron, N. Dershowitz, A. Rabinovich, Eds.), vol. 4800 of LNCS, Springer-Verlag, 2008, 460–474.
• [32] Lomazova, I. A., van Hee, K. M., Oanea, O., Serebrenik, A., Sidorova, N., Voorhoeve, M.: Nested Nets for Adaptive Systems, Application and Theory of Petri Nets, LNCS, Springer-Verlag, 2006.
• [33] Lomazova, I. A., Schnoebelen, P.: Some Decidability Results for Nested Petri Nets, Perspectives of System Informatics (PSI’99), 1755, Springer-Verlag, 2000.
• [34] Ma, L., Tsai, J.: Security Modeling And Analysis of Mobile Agent Systems, Imperial College Press, 2006.
• [35] Mayr, E. W.: An Algorithm for the General Petri Net Reachability Problem, SIAM Journal Computation, 13(3), August 1984, 441–460.
• [36] Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, parts 1-2, Information and computation, 100(1), 1992, 1–77.
• [37] Peterson, J.: Petri Net Theory and the Modeling of Systems, Prentice Hall Inc., Englewood Cliffs NJ, 1981.
• [38] Peterson, J. L., Silberschatz, A.: Operating System Concepts, Addison-Wesley Publishing Company, Reading, Massachusetts, 1985, Second edition.
• [39] Petri, C. A.: Introduction to general net theory, Net Theory and its applications. Proceedings of the Advanced course on general net theory of processes and systems (W. Brauer, Ed.), 84, Springer-Verlag, 1979.
• [40] Petri, C. A.: Nets, Time and Space, Theoretical Computer Science, 153(1&2), 1996, 3–48.
• [41] Valk, R.: Modelling Concurrency by Task/Flow EN Systems, 3rd Workshop on Concurrency and Compositionality, number 191 in GMD-Studien, Gesellschaft f¨ur Mathematik und Datenverarbeitung, Bonn, 1991.
• [42] Valk, R.: Petri Nets as Token Objects: An Introduction to Elementary Object Nets, Application and Theory of Petri Nets (J. Desel, M. Silva, Eds.), 1420, 1998.
• [43] Valk, R.: Object Petri nets: Using the nets-within-nets paradigm, Advanced Course on Petri Nets 2003 (J. Desel, W. Reisig, G. Rozenberg, Eds.), 3098, Springer-Verlag, 2003.
• [44] Velardo, F. R., de Frutos-Escrig, D.: Name Creation vs. Replication in Petri Net Systems, Fundam. Inform., 88(3), 2008, 329–356.
• [45] Xu, D., Deng, Y.: Modeling Mobile Agent Systems with High Level Petri Nets, IEEE International Conference on Systems, Man, and Cybernetics’2000, 2000.