Conservative Elementary Object Systems

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

Abstrakty

EN

This contribution presents decidability results for the formalism of 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 paper we study the relationship of the reachability and the liveness problem. We prove that both problems are undecidable for EOS (even for the subclass of conservative EOS) while it is well known that both are decidable for classical p/t nets. Despite these undecidability results, boundedness can be decided for conservative EOS using a monotonicity argument similar to that for p/t nets.

Słowa kluczowe

EN

Petri net; nets-within-net; nets as tokens; reachability; liveness; boundedness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 3/4
• Strony: 325--339
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Köhler-Bußmeier M.

autor

Heitmann F.

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

Bibliografia

• [1] Bednarczyk, M. A., Bernardinello, L., Pawlowski,W., Pomello, L.: Modelling mobility with Petri hypernets, Recent Trends in Algebraic Development Techniques (WADT 2004) (J. L. Fiadeiro, P. D. Mosses, F. Orejas, Eds.), 3423, Springer-Verlag, 2004.
• [2] 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.
• [3] Finkel, A., Schnoebelen, P.: Well-structured Transition systems everywhere!, Theoretical Computer Science, 256(1-2), 2001, 63-92.
• [4] Hack, M.: Petri Net Language, Technical report, Cambridge, MA, USA, 1976.
• [5] 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.
• [6] Köhler, M.: Reachable Markings of Object Petri Nets, Fundamenta Informaticae, 79(3-4), 2007, 401 - 413.
• [7] 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.
• [8] 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.
• [9] 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.
• [10] Köhler-Bußmeier, M.: Hornets: Nets within Nets combined with Net Algebra, Application and Theory of Petri Nets (ICATPN'2009) (K. Wolf, G. Franceschinis, Eds.), 5606, Springer-Verlag, 2009.
• [11] Köhler-Bußmeier, M.: A Survey of Elementary Object Systems: Decidability Results, Technical report, Universität Hamburg, 2011, http://edoc.sub.uni-hamburg.de/informatik/volltexte/2011/174/.
• [12] Köhler-Bußmeier, M., Heitmann, F.: Safeness for Object Nets, Fundamenta Informaticae, 101(1-2), 2010, 29-43.
• [13] Kummer, O.: Undecidability in Object-Oriented Petri Nets, Petri Net Newsletter, 59, 2000, 18-23.
• [14] Lomazova, I. A., van Hee, K. M., Oanea, O., Serebrenik, A., Sidorova, N., Voorhoeve, M.: Nested Nets for Adaptive Systems, Theory of Petri Nets and Other Models of Concurrency, LNCS, Springer-Verlag, 2006.
• [15] Lomazova, I. A., Schnoebelen, P.: Some Decidability Results for Nested Petri Nets, Perspectives of System Informatics (PSI'99), 1755, Springer-Verlag, 2000.
• [16] Peterson, J.: Petri Net Theory and the Modeling of Systems, Prentice Hall Inc., Englewood Cliffs NJ, 1981.
• [17] 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.
• [18] Velardo, F. R., de Frutos-Escrig, D.: Name Creation vs. Replication in Petri Net Systems, Fundamenta Informaticae, 88(3), 2008, 329-356.