Safeness for Object Nets

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

Abstrakty

EN

In this paper we discuss the concept of safeness for Elementary Object Nets (EOS). Object nets are Petri nets which have Petri nets as tokens – an approach known as the nets-within-nets paradigm. Object nets are called elementary if the net system has a two levelled structure. The well known p/t nets can be considered as a special case of EOS. For p/t nets the concept of safeness means that there is at most one token on each place. Since object nets have nested markings there are different possibilities to generalise this idea for EOS. In this paper we define different variants of EOS safeness, discuss their relationships, show that they all coincide for p/t-like EOS, and address the complexity of well known Petri net problems like reachability and liveness for this new class of object nets.

Słowa kluczowe

EN

Elementary Object Nets (EOS); Petri net; object Petri-net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 101, nr 1/2
• Strony: 29--43
• Opis fizyczny: Bibliogr. 21 poz., wykr.

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, Germany,

Bibliografia

• [1] M. A. Bednarczyk, L. Bernardinello, W. Pawlowski, and L. Pomello. Modelling mobility with Petri hypernets. In J. L. Fiadeiro, P. D. Mosses, and F. Orejas, editors, Recent Trends in Algebraic Development Techniques (WADT 2004), volume 3423 of LNCS, pages 28-44. Springer, 2004.
• [2] J. Esparza. Decidability and complexity of Petri net problems - an introduction. In W. Reisig and G. Rozenberg, editors, Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, volume 1491 of LNCS, pages 374-428. Springer, 1998.
• [3] S. Haddad and D. Poitrenaud. Theoretical aspects of recursive Petri nets. In S. Donatelli and J. Kleijn, editors, Application and Theory of Petri Nets, volume 1639 of LNCS, pages 228-247. Springer, 1999.
• [4] K. Hiraishi. PN2: An elementary model for design and analysis of multi-agent systems. In F. Arbab and C. L. Talcott, editors, Coordination Models and Languages, COORDINATION 2002, volume 2315 of LNCS, pages 220-235. Springer, 2002.
• [5] K. Hoffmann, H. Ehrig, and T. Mossakowski. High-level nets with nets and rules as tokens. In Application and Theory of Petri Nets and Other Models of Concurrency, volume 3536 of LNCS, pages 268 - 288. Springer, 2005.
• [6] N. D. Jones, L. H. Landweber, and Y. E. Lien. Complexity of some problems in petri nets. Theoretical Computer Science, 4:277-299, 1977.
• [7] M. Köhler. Reachable markings of object Petri nets. Fundamenta Informaticae, 79(3-4):401 - 413, 2007.
• [8] M. Köhler, D. Moldt, and H. Rölke. Modeling the behaviour of Petri net agents. In J. M. Colom and M. Koutny, editors, Application and Theory of Petri Nets, volume 2075 of LNCS, pages 224-241. Springer, 2001.
• [9] M. Köhler, D. Moldt, and H. Rölke. Modelling mobility and mobile agents using nets within nets. InW. v. d. Aalst and E. Best, editors, Application and Theory of Petri Nets 2003, volume 2679 of LNCS, pages 121-140. Springer, 2003.
• [10] M. Köhler and H. Rölke. Concurrency for mobile object-net systems. Fundamenta Informaticae, 54(2-3), 2003.
• [11] M. Köhler and H. Rölke. Properties of Object Petri Nets. In J. Cortadella andW. Reisig, editors, Application and Theory of Petri Nets 2004, volume 3099 of LNCS, pages 278-297. Springer, 2004.
• [12] M. Köhler-Bußmeier. Hornets: Nets within nets combined with net algebra. In K.Wolf and G. Franceschinis, editors, Application and Theory of Petri Nets 2009, volume 5606 of LNCS, pages 243-262. Springer, 2009.
• [13] O. Kummer, R. Dietze, and M. Kudlek. Decidability problems of a basic class of object nets. Fundamenta Informaticae, 79(3-4):295-302, 2008.
• [14] C. Lakos. A Petri net view ofmobility. In Formal Techniques for Networked and Distributed Systems (FORTE 2005), volume 3731 of LNCS, pages 174-188. Springer, 2005.
• [15] I. A. Lomazova. Nested Petri nets - a formalism for specification of multi-agent distributed systems. Fundamenta Informaticae, 43(1-4):195-214, 2000.
• [16] W.J. Savitch. Relationship between nondeterministic and deterministic tape complexities. J. on Computer and System Sciences, 4:177-192, 1970.
• [17] I. A. Lomazova, K. M. van Hee, O. Oanea, A. Serebrenik, N. Sidorova, and M. Voorhoeve. Nested nets for adaptive systems. In Application and Theory of Petri Nets and Other Models of Concurrency, LNCS, pages 241-260. Springer, 2006.
• [18] R. Valk. Modelling concurrency by task/flow EN systems. In 3rd Workshop on Concurrency and Compositionality, number 191 in GMD-Studien, St. Augustin, Bonn, 1991. Gesellschaft für Mathematik und Datenverarbeitung.
• [19] R. Valk. Petri nets as token objects: An introduction to elementary object nets. In J. Desel and M. Silva, editors, Application and Theory of Petri Nets, volume 1420 of LNCS, pages 1-25, 1998.
• [20] R. Valk. Object Petri nets: Using the nets-within-nets paradigm. In J. Desel, W. Reisig, and G. Rozenberg, editors, Advanced Course on Petri Nets 2003, volume 3098 of LNCS, pages 819-848. Springer, 2003.
• [21] M. Vardi. An Automata-TheoreticApproach to Linear temporal Logic. In F.Moller and G. Birtwistle, editors, Logics for Concurrency: Structure versus Automata, volume 1043 of LNCS, pages 238-266. Springer, 1996.