Nets in nets (petri nets)

from Wikipedia, the free encyclopedia

Nets in nets are a modeling approach from the Petri net family.

They stand out from other types of Petri nets by the possibility of providing brands with an internal structure that in turn functions on the basis of Petri nets. A network can therefore contain other network copies that are moved around in it and can switch themselves in the process.

motivation

Networks in networks are suitable for modeling distributed systems with special attention to aspects of the

  • Hierarchy,
  • Mobility and
  • Encapsulation

In many developments, a strong reference to object orientation was intentionally sought in order to combine the ability of Petri nets to model concurrent processing with modeling with objects that can be created and interact.

history

On the basis of practical requirements, various formalisms have been developed since the mid-1990s to which the description "networks in networks" fits. In the article mentioned, Lomazova and Schnoebelen list some that are generally known: Sibertin-Blanc, Lakos, Moldt and Wienberg as based on colored Petri nets, as well as the object nets by Valk.

The earliest use of hierarchical network models can be found at Valk and Jessen, where Valk introduced the so-called "Task / Flow Nets" in an article in order to be able to model order systems in a compact manner. In these models, orders run as brands through a network that models their processing; At the same time, the individual orders each have an internal status that saves their history and shows to what extent they have already been processed.

Semantics

The main distinction in the interpretation takes place in the treatment of the marks. Are trademarks only references to network specimens that coexist in a given global state, it is a reference semantics , brands, however, are to be interpreted even as networks, there is a value semantics before. These differ in the treatment of brands of the same type: Network brands in value semantics exist independently of one another and each have their own status.

A problem does not necessarily arise when copying, but at the latest when merging different copies of "the same" network. Sometimes a third type of semantic suggested in the article makes sense here. With this variant of the value semantics, the process histories of the copies are merged into the smallest process history, which contains both.

Mixed forms are also possible and sometimes relevant in terms of modeling.

communication

Without communication between the network instances, very little can be modeled; As in object-oriented programming , the formalisms therefore usually offer communication between the objects (network copies) via predefined interfaces, which, however, are dynamically linked.

Figure 1: Nested Petri net with channel addresses

Figure 1 shows an example of a network that includes another network. This example is designed so simply that value and reference semantics coincide. The inner network is movable and can be switched as a token from location "a" to location "b"; the channel addresses act like method calls and ensure that this external state is reflected in the internal network after the "calling" and "called" transitions have been synchronized. The "x" at the edges is a variable that is linked to the network marker when a transition of the outer network is switched.

Algorithms and Restricted Formalisms

Classic Petri net properties such as accessibility , limitation and liveliness can only be partially determined . The work of Köhler-Bußmeier gives an overview of decidability issues in elementary object networks. In order to reduce the complexity, subclasses were defined by restricting the structure of the underlying Petri nets, for example as a state machine. Such restrictions still allow the complex modeling of e.g. B. mobile systems, but have polynomial complexity in model checking .

Tools

References

  1. ↑ Michael Köhler-Bußmeier: Object Networks: Definition and Properties , Logos-Verlag, Berlin, 2004
  2. ↑ Irina A. Lomazova and Philippe Schnoebelen: Some decidability results for nested Petri nets , Perspectives of System Informatics, pp. 208-220, Springer 2000
  3. ↑ C. Sibertin-Blanc: Cooperative nets , Application and Theory of Petri Nets 1994, pp. 471-490, Springer 1994
  4. ^ Charles Lakos: From colored Petri nets to object Petri nets , Application and Theory of Petri Nets 1995, pp 278--297, 1995, Springer
  5. ^ Daniel Moldt and Frank Wienberg: Multi-agent-systems based on colored Petri nets, Application and Theory of Petri Nets 1997, pp. 82-101, Springer 1997
  6. ^ Rüdiger Valk: Petri nets as token objects , Application and Theory of Petri-Nets, pp. 1-24, Springer, 1998
  7. ^ Eike Jessen, Rudiger Valk: Computing systems: Fundamentals of modeling, study series computer science , 1987, Springer, Heidelberg
  8. ^ Rüdiger Valk: Object Petri Nets , Lectures on Concurrency and Petri Nets, p. 819-848, Springer 2004
  9. ^ Rüdiger Valk: Object Petri Nets , Lectures on Concurrency and Petri Nets, pp. 819-848, Springer 2004
  10. ↑ Berndt Farwer and Michael Köhler: Modeling global and local name spaces for mobile agents using object nets , Fundamenta Informaticae, Vol. 72, No 1, pp. 109-122, IOS Press 2006
  11. ↑ Michael Köhler-Bußmeier: A Survey of Decidability Results for Elementary Object Systems : Fundamenta Informaticae, Vol. 130, No 1, pp. 99-123, 2014
  12. ↑ Frank Heitmann, Michael Köhler-Bußmeier: P- and t-systems in the nets-within-nets formalism : Springer LNCS 7347, 2012, pp. 368-387
  13. ^ Olaf Kummer: Reference networks , dissertation, University of Hamburg, Logos Verlag Berlin 2002