Nets within Nets

Last updated

Nets within Nets is a modelling method belonging to the family of Petri nets. This method is distinguished from other sorts of Petri nets by the possibility to provide their tokens with a proper structure, which is based on Petri net modelling again. Hence, a net can contain further net items, being able to move around and fire themselves.

Petri net

A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places. The directed arcs describe which places are pre- and/or postconditions for which transitions. Some sources state that Petri nets were invented in August 1939 by Carl Adam Petri—at the age of 13—for the purpose of describing chemical processes.

Contents

Motivation

Nets within nets are well suited for the modelling of distributed systems under the particular aspects of

In a lot of publications in relation to object-oriented design is given, in order to combine the ability of Petri nets in modelling distributed computing with the modelling of objects, being able to be created and to interact.

Object-oriented design is the process of planning a system of interacting objects for the purpose of solving a software problem. It is one approach to software design.

History

Starting from the need of practical applications, by the mid of nineties, different formalisms have been created, which fit the description of „nets within nets“. Lomazova and Schnoebelen are listing [1] some of these approaches, namely by Sibertin-Blanc, [2] Lakos, [3] Moldt und Wienberg [4] as extending Coloured Petri nets, aside the Object Nets of Valk. [5] The earliest use of such hierarchic net models appeared by Rüdiger Valk in Valk and Jessen, [6] where the so-called task-flow nets [7] are introduced in order to model task systems in operating systems. In these models tasks are modelled by a Petri net, which represents the precedences of tasks and their state of execution.

Coloured Petri nets (CPN) are a backward compatible extension of the concept of Petri nets.

Rüdiger Valk is a German mathematician. From 1976 to 2010 he was Professor for Theoretical Computer Science (Informatics) at the Institut für Informatik of the University of Hamburg, Germany.

Semantics

The most important differences in semantics is given by the execution of net tokens. On the one side net tokens can be references to net items, [8] which case is called „reference semantics“. This kind of semantic is distinguished from value semantics, where net objects may exist in different places and different internal states. In value semantics different copies can be created to model concurrent execution. The corresponding join of such a split can be defined in different ways, as for instance by „distributed token semantics“ [9] or „history process semantics“. [10] In connection with mobile computing hybrid versions of reference and value semantics are of importance. [11] In distributed token semantics the important calculus of place invariants for Petri nets remains valid. [12]

In computer science, having value semantics means for an object that only its value counts, not its identity. If the concept is fully applied, value semantics implies immutability of the object.

Communication

The formalism of nets within nets would be of few importance without communication between net tokens. Like in object-oriented programming communication of net tokens is introduced via predefined interfaces which are dynamically bound.

Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data, in the form of fields, and code, in the form of procedures. A feature of objects is an object's procedures that can access and often modify the data fields of the object with which they are associated. In OOP, computer programs are designed by making them out of objects that interact with one another. OOP languages are diverse, but the most popular ones are class-based, meaning that objects are instances of classes, which also determine their types.

Figure 1: Nested Petri net containing channels via inscriptions Forthandback.svg
Figure 1: Nested Petri net containing channels via inscriptions

In Figure 1 a Petri net is shown containing a token Petri net in place „a“. The token net can move around from place „a“ to place „b“ and back by firing of the transitions of the outer net. The channel inscriptions at the transitions behave like a call of a method, resulting in the synchronised firing of the calling transition in the outer net [e.g. labelled by x:forth()] and the called transition [e.g. labelled by :forth()] in the token net. The variable „x“ at an arrow is bound to the token net in the place connected with this arrow. The brackets may contain parameters to be passed. This example is so simple that reference and value semantics coincide.

A method in object-oriented programming (OOP) is a procedure associated with a message and an object. An object consists of data and behavior. The data and behavior comprise an interface, which specifies how the object may be utilized by any of various consumers of the object.

Algorithms and restricted formalisms

Standard Petri net properties like reachability, boundedness and liveness show a mixed picture. A paper [13] of Köhler-Bußmeier gives a survey on decidability results for elementary object systems. To reduce the complexity of the formalism subclasses have been defined by restricting the structure of the Petri nets, as for instance to state machines. Such restrictions still allow complex modelling of distributed and mobile systems, but have polynomial complexity in model checking. [14]

Tools

Related Research Articles

In computer science, denotational semantics is an approach of formalizing the meanings of programming languages by constructing mathematical objects that describe the meanings of expressions from the languages. Other approaches provide formal semantics of programming languages including axiomatic semantics and operational semantics.

In computer science, specifically software engineering and hardware engineering, formal methods are a particular kind of mathematically based technique for the specification, development and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the expectation that, as in other engineering disciplines, performing appropriate mathematical analysis can contribute to the reliability and robustness of a design.

In computer science, model checking or property checking is, for a given model of a system, exhaustively and automatically checking whether this model meets a given specification. Typically, one has hardware or software systems in mind, whereas the specification contains safety requirements such as the absence of deadlocks and similar critical states that can cause the system to crash. Model checking is a technique for automatically verifying correctness properties of finite-state systems.

Concurrency (computer science)

In computer science, concurrency refers to the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the final outcome. This allows for parallel execution of the concurrent units, which can significantly improve overall speed of the execution in multi-processor and multi-core systems. In more technical terms, concurrency refers to the decomposability property of a program, algorithm, or problem into order-independent or partially-ordered components or units.

The actor model in computer science is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent computation. In response to a message that it receives, an actor can: make local decisions, create more actors, send more messages, and determine how to respond to the next message received. Actors may modify their own private state, but can only affect each other through messages.

The CO-OPN specification language is based on both algebraic specifications and algebraic Petri nets formalisms. The former formalism represent the data structures aspects, while the latter stands for the behavioral and concurrent aspects of systems. In order to deal with large specifications some structuring capabilities have been introduced. The object-oriented paradigm has been adopted, which means that a CO-OPN specification is a collection of objects which interact concurrently. Cooperation between the objects is achieved by means of a synchronization mechanism, i.e., each object event may request to be synchronized with some methods of one or a group of partners by means of a synchronization expression.

Kahn process networks

Kahn process networks is a distributed model of computation where a group of deterministic sequential processes are communicating through unbounded FIFO channels. The resulting process network exhibits deterministic behavior that does not depend on the various computation or communication delays. The model was originally developed for modeling distributed systems but has proven its convenience for modeling signal processing systems. As such, KPNs have found many applications in modeling embedded systems, high-performance computing systems, and other computational tasks. KPNs were first introduced by Gilles Kahn.

In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation.

Activity diagram diagram that models activity and process flows

Activity diagrams are graphical representations of workflows of stepwise activities and actions with support for choice, iteration and concurrency. In the Unified Modeling Language, activity diagrams are intended to model both computational and organizational processes, as well as the data flows intersecting with the related activities. Although activity diagrams primarily show the overall flow of control, they can also include elements showing the flow of data between activities through one or more data stores.

In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation. This article reports on the later history of the Actor model in which major themes were investigation of the basic power of the model, study of issues of compositionality, development of architectures, and application to Open systems. It is the follow on article to Actor model middle history which reports on the initial implementations, initial applications, and development of the first proof theory and denotational model.

YAWL is a workflow language based on workflow patterns. The language is supported by a software system that includes an execution engine, a graphical editor and a worklist handler. The system is available as Open source software under the LGPL license.

Dualistic Petri nets (dPNs) are a process-class variant of Petri nets. Like Petri nets in general and many related formalisms and notations, they are used to describe and analyze process architecture.

Semantic data model

Semantic data model is a high-level semantics-based database description and structuring formalism for databases. This database model is designed to capture more of the meaning of an application environment than is possible with contemporary database models. An SDM specification describes a database in terms of the kinds of entities that exist in the application environment, the classifications and groupings of those entities, and the structural interconnections among them. SDM provides a collection of high-level modeling primitives to capture the semantics of an application environment. By accommodating derived information in a database structural specification, SDM allows the same information to be viewed in several ways; this makes it possible to directly accommodate the variety of needs and processing requirements typically present in database applications. The design of the present SDM is based on our experience in using a preliminary version of it. SDM is designed to enhance the effectiveness and usability of database systems. An SDM database description can serve as a formal specification and documentation tool for a database; it can provide a basis for supporting a variety of powerful user interface facilities, it can serve as a conceptual database model in the database design process; and, it can be used as the database model for a new kind of database management system.[5]

Enterprise engineering is defined as the body of knowledge, principles, and practices to design all or part of an enterprise. An enterprise is a complex, socio-technical system that comprises interdependent resources of people, information, and technology that must interact with each other and their environment in support of a common mission. According to Kosanke, Vernadat and Zelm, enterprise engineering is an enterprise life-cycle oriented discipline for the identification, design, and implementation of enterprises and their continuous evolution, supported by enterprise modelling. Enterprise engineering is a subdiscipline of industrial engineering / systems engineering. The discipline examines each aspect of the enterprise, including business processes, information flows, material flows, and organizational structure. Enterprise engineering may focus on the design of the enterprise as a whole, or on the design and integration of certain business components.

Algebraic Petri net

An algebraic Petri net (APN) is an evolution of the well known Petri net in which elements of user defined data types replace black tokens. This formalism can be compared to coloured Petri nets (CPN) in many aspects. However, in the APN case, the semantics of the data types is given by an axiomatization enabling proofs and computations on it.

TAPAAL Model Checker

TAPAAL is a tool for modelling, simulation and verification of Timed-Arc Petri nets developed at Department of Computer Science at Aalborg University in Denmark and it is available for Linux, Windows and Mac OS X platforms.

RP, the International Conference on Reachability Problems is an annual academic conference in the field of computer science.

In computer science, especially model checking and abstract interpretation, widening refers to at least two different techniques in the analysis of abstract transition systems where infinite progressions of abstract states are replaced by a least fixed point. The use of the term in model checking is closely related to acceleration techniques, some authors reserving acceleration for exact computations.

References

  1. ↑ Irina A. Lomazova, Philippe Schnoebelen: Some decidability results for nested Petri nets, Springer LNCS 1755, 2000, pp. 208-220
  2. ↑ Christophe Sibertin-Blanc: Cooperative Nets, Springer LNCS 815, 1994, pp. 471-490
  3. ↑ Charles Lakos: From coloured Petri nets to object Petri nets, Springer LNCS 935, 1995, pp. 278-297
  4. ↑ Daniel Moldt und Frank Wienberg: Multi-agent-systems based on coloured Petri nets, Springer LNCS 1248, 1997, pp. 82-101
  5. ↑ Rüdiger Valk: Petri nets as token objects, Springer LNCS 1420, 1998, pp. 1-24
  6. ↑ Eike Jessen, Rüdiger Valk: Rechensysteme: Grundlagen der Modellbildung, Springer, 1987
  7. ↑ Rüdiger Valk: Modelling Concurrency by Task/Flow EN Systems. Proceedings 3rd Workshop on Concurrency and Compositionality, GMD-Studien Nr. 191, Bonn, 1991
  8. ↑ Olaf Kummer: Referenznetze, Dissertation, Universität Hamburg, Logos Verlag Berlin 2002
  9. ↑ Michael Köhler, Heiko Rölke: Properties of Object Petri Nets. Springer LNCS 3099, 2004, pp. 278-297
  10. ↑ Rüdiger Valk: Object Petri Nets, Springer LNCS 3098, 2004, pp. 819-848
  11. ↑ Berndt Farwer, Michael Köhler: Modelling global and local name spaces for mobile agents using object nets, Fundamenta Informaticae, Vol. 72, No 1, pp. 109-122, 2006
  12. ↑ Michael Köhler-Bußmeier, Daniel Moldt: Analysis of mobile agents using invariants of object nets. Electronic Communications of the EASST: Special Issue on Formal Modeling of Adaptive and Mobile Processes, 12, 2009. http://www.easst.org/eceasst/
  13. ↑ Michael Köhler-Bußmeier: A Survey of Decidability Results for Elementary Object Systems: Fundamenta Informaticae, Vol. 130, No 1, pp. 99-123, 2014
  14. ↑ Frank Heitmann, Michael Köhler-Bußmeier: P- and t-systems in the nets-within-nets formalism: Springer LNCS 7347, 2012, pp. 368-387
  15. ↑ Olaf Kummer, Frank Wienberg, Michael Duvigneau, Jörn Schumacher, Michael Köhler, Daniel Moldt, Heiko Rölke, Rüdiger Valk, : An Extensible Editor and Simulation Engine for Petri Nets: Renew: Springer LNCS 3099, 2004, pp. 484-493
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.