Structural and Dynamic Restrictions of Elementary Object Systems

• Autorzy: Heitmann F. , Köhler-Bußmeier M.

Identyfikatory

DOI

10.3233/FI-2014-1130

• Języki publikacji: EN

Abstrakty

EN

Elementary object systems (EOS for short) are Petri nets in which tokens may be Petri nets again. Originally proposed by Valk for a two levelled structure, the formalism was later generalised for arbitrary nesting structures. However, even if restricted to a nesting depth of two, EOS are Turing-complete and thus many problems like reachability and liveness are undecidable for them. Nonetheless, since they are useful to model many practical applications a natural question is how to restrict the formalism in such a way, that the resulting restricted formalism is still helpful in a modelling context, but so that important verification problems like reachability become quickly decidable. In the last years several structural and dynamic restrictions for EOS have therefore been investigated. These investigations have been central to the first author’s recent PhD thesis and have been published in past editions of this journal and on conferences. In this paper we add several new results and present them together with the old in a unified fashion highlighting the central message of these investigations.

Słowa kluczowe

EN

high-level Petri net models; nets-within-nets; restrictions; reachability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 4
• Strony: 387--401
• Opis fizyczny: Bibliogr. 32 poz., rys., tab.

Twórcy

autor

Heitmann F.

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

autor

Köhler-Bußmeier M.

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

Bibliografia

• [1] Bednarczyk, M. A., Jamroga, W., Pawłowski, W.: Expressing and Verifying Temporal and Structural Properties of Mobile Agents, Fundamenta Informaticae, 72(1-3), 2006, 51–63.
• [2] Cardelli, L., Gordon, A. D.: Mobile Ambients, Theoretical Computer Science, 240, 2000, 177–213.
• [3] Castagna, G., Vitek, J., Nardelli, F. Z.: The Seal Calculus, Information and Computation, 201, 2005, 1–54.
• [4] Charatonik, W., Zilio, S. D., Gordon, A. D., Mukhopadhyay, S., Talbot, J.-M.: Model checking mobile Ambients, Theoretical Computer Science, 308, 2003, 277–331.
• [5] Dworzański, L. W., Lomazova, I. A.: On Compositionality of Boundedness and Liveness for Nested Petri Nets, Concurrency, Specification and Programming (CS&P 2011), Proceedings (M. Szczuka, L. Czaja, A. Skowron, M. Kacprzak, Eds.), Białystok University of Technology, Pułtusk, Poland, 2011.
• [6] Dworzański, L. W., Lomazova, I. A.: On Compositionality of Boundedness and Liveness for Nested Petri Nets, Fundamenta Informaticae, 120(3–4), 2012, 275–293.
• [7] 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.
• [8] 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.
• [9] Heitmann, F.: Algorithms and Hardness Results for Object Nets, Ph.D. Thesis, University of Hamburg, 2013.
• [10] Heitmann, F., Köhler-Bußmeier, M.: On Defining Conflict-Freedom for Object Nets, Proceedings of the Second International Workshop on Logic, Agents, and Mobility (LAM 2011) (B. Farwer, M. Köhler-Bußmeier, Eds.), 2011.
• [11] Heitmann, F., Köhler-Bußmeier, M.: P- and T-Systems in the Nets-within-Nets-Formalism, Application and Theory of Petri Nets. 33rd International Conference, PETRI NETS 2012. Hamburg, Germany, June 2012. Proceedings (S. Haddad, L. Pomello, Eds.), 7347, Springer-Verlag, 2012.
• [12] 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.
• [13] 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.
• [14] Köhler, M.: The Reachability Problem for Object Nets, Fundamenta Informaticae, 79(3-4), 2007, 401 – 413.
• [15] Köhler, M., Moldt, D., Rölke, H.: Modeling the Behaviour of Petri Net Agents, Application and Theory of Petri Nets (J. M. Colom, M. Koutny, Eds.), 2075, Springer-Verlag, 2001.
• [16] Köhler, M., Moldt, D., Rölke, H.: Modelling Mobility and Mobile Agents using Nets within Nets, Application and Theory of Petri Nets (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 (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 (G. Ciardo, P. Darondeau, Eds.), 3536, Springer-Verlag, 2005.
• [20] Köhler-Bußmeier, M.: Decidability results for elementary object systems, Report of the department of informatics, Universität Hamburg, Fachbereich Informatik, 2011.
• [21] Köhler-Bußmeier, M., Heitmann, F.: Safeness for Object Nets, Fundamenta Informaticae, 101(1-2), 2010, 29–43.
• [22] Köhler-Bußmeier, M., Heitmann, F.: Liveness of Safe Object Nets, Fundamenta Informaticae, 112(1), 2011, 73–87.
• [23] Köhler-Bußmeier, M., Heitmann, F.: Conservative Elementary Object Systems, Fundamenta Informaticae, 120(3–4), 2012, 325–339.
• [24] Köhler-Bußmeier, M., Heitmann, F.: Complexity Results for Elementary Hornets, Application and Theory of Petri Nets and Concurrency. 34th International Conference, PETRI NETS 2013. Milan, Italy, June 24-28, 2013. Proceedings (J.-M. Colom, J. Desel, Eds.), 7927, Springer-Verlag, 2013.
• [25] Lakos, C.: A Petri Net View of Mobility, Formal Techniques for Networked and Distributed Systems (FORTE 2005), 3731, Springer-Verlag, 2005.
• [26] Lomazova, I. A.: Nested Petri Nets – a Formalism for Specification of Multi-agent distributed systems, Fundamenta Informaticae, 43(1-4), 2000, 195–214.
• [27] Lomazova, I. A., van Hee, K. M., Oanea, O., Serebrenik, A., Sidorova, N., Voorhoeve, M.: Nested Nets for Adaptive Systems, Petri Nets and Other Models of Concurrency - ICATPN 2006. 27th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, Turku, Finland, June 26-30, 2006. Proceedings, 4024, Springer-Verlag, 2006.
• [28] Ma, L., Tsai, J. J. P., Murata, T.: A Secure Mobile Agent System Model Based on Extended Elementary Object System, 28th International Computer Software and Applications Conference (COMPSAC 2004), Design and Assessment of Trustworthy Software-Based Systems, 27-30 September 2004, Hong Kong, China, Proceedings, IEEE Computer Society, 2004.
• [29] Reisig, W., Rozenberg, G., Eds.: Lectures on Petri Nets I: Basic Models, vol. 1491 of Lecture Notes in Computer Science, Springer-Verlag, 1998.
• [30] Valk, R.: Modelling Concurrency by Task/Flow EN Systems, 3rd Workshop on Concurrency and Compositionality, number 191 in GMD-Studien, Gesellschaft für Mathematik und Datenverarbeitung, St. Augustin, Bonn, 1991.
• [31] 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, 2004.
• [32] Vardi, M.: An Automata-Theoretic Approach to Linear temporal Logic, Logics for Concurrency: Structure versus Automata (F. Moller, G. Birtwistle, Eds.), 1043, Springer-Verlag, 1996.