HomeNewsReferencesChronologyPresentationsOPNs

LLPN - Linear Logic Petri Nets
What are Object Petri Nets?

Essentially, Object Petri Nets (OPNs) are Petri nets that use Petri nets as tokens. The tokens are then usually called object nets or token nets. The top-level net is called system net.

The idea generalises an earlier approach of Valk using task systems as tokens in task flow nets. All of these approaches can be summed up under the nets-within-nets paradigm.

So, you might ask: "How do OPNs work?"

The simple answer to this queston is: Just like ordinary Petri nets do!

... but this does not take into account some of the subtleties of the formalism. Actually, at this point there is no one-and-only recognised OPN formalism, but instead there are several different approaches, that have some things in common and diverge in some other aspects.

Let's start with what they have in common. On the one hand, they all have some concept of synchronisation to allow for communication or interaction. On the other hand, autonomous actions are allowed, as long as no synchronisation requirements are specified for those actions.

To complicate things further, there are two different kinds of semantics considered in the literature: value semantics and reference semantics. In the former, fork transitions actually produce copies of the object net in its output places. These copies can evolve individually and the problem arises, what to do when the copies meet at a join transition. Now it depends on the intention of the net, whether one wants to check if the individual copies have evolved in a consistent way (Valk's process markings) or whether it is regarded as sufficient that there are token nets in the input places and some other action is performed to determine the object nets to be produced on the output places. Reference Semantics avoids this problem by regarding the tokens as pointers to a net which is globally accessed, so that a fork transition only produces several pointers to the same object net, such that inconsistent evolutions of the object nets cannot happen. The most prominent example of such a formalism is the reference-nets formalism by Kummer [Kum02] together with the Renew tool, which is now available in version 2.0.

An attempt to provide a formalism combining value semantics and reference semantics has been proposed in [FK05a]. Such formalism is desirable for a more natural representation of objects that can be copied (e.g., a sheet of paper used as a form) and objects that cannot (e.g. living creatures). This has been first suggested in [Far00b] and [Far01a].

The problem of control/data separation in Petri nets is addressed using object Petri nets e.g. in [FV05]. Verification of OPNs is discussed in [FL04] where an encoding of object Petri nets into executable Prolog programs is used for model checking.

Some references:

[ACR01] G.A. Agha, F. De Cindio, and G. Rozenberg, editors. Concurrent Object-Oriented Programming and Petri Nets. LNCS 2001. Springer-Verlag, 2001.

[Far96] B. Farwer. Relating object systems to formulae of infinitary linear logic. Talk given at the Third Seminar on Algebra, Logic, and Geometry in Informatics (ALGI 3), Tokyo, 1996.

[Far98a] B. Farwer. A linear logic view of object systems. In H.-D. Burkhard, L. Czaja, and P. Starke, editors, Concurrency Specification and Programming (CSP'98), Proceedings, pages 76-87. Humboldt-Universität, Berlin, 1998.

[Far98b] B. Farwer. Towards linear logic Petri nets - From P/T-nets to object systems. Technical report, FBI-HH-B-211/98, Fachbereich Informatik, Universität Hamburg, 1998.

[Far99a] B. Farwer. Linear Logic Based Calculi for Object Petri Nets. PhD thesis, Universität Hamburg, Fachbereich Informatik, Vogt-Kölln-Str. 30, D-22527 Hamburg, 1999.

[Far99b] B. Farwer. A linear logic view of object Petri nets. Fundamenta Informaticae, 37(3):225-246, 1999.

[Far00a] B. Farwer. Linear Logic Based Calculi for Object Petri Nets. Logos Verlag, ISBN 3-89722-539-5, Berlin, 2000.

[Far00b] B. Farwer. Relating formalisms for non-object-oriented object Petri nets. In P. Starke L. Czaja, editor, Concurrency, Specification, and Programming (CSP'2000). Proceedings. Volume 1, pages 53-64. Humboldt-Universität, Berlin, 2000.

[Far01a] B. Farwer. Comparing concepts of object Petri net formalisms. Fundamenta Informaticae, 47(3-4):247-258, 2001.

[Far01b] B. Farwer. Modelling protocols by object-based Petri nets. In L. Czaja, editor, Concurrency Specification and Programming (CSP'01), Proceedings, pages 87-96. University of Warsaw, 2001.

[Far02] B. Farwer. Dynamic modification of object Petri nets. an application to modelling protocols with fork-join structures. Fundamenta Informaticae, 51(1,2):91-101, 2002.

[FK03a] B. Farwer and M. Köhler. Mobile object-net systems and their processes. In L. Czaja, editor, Concurrency, Specification, and Programming CS&P'2003 (Volume 1)

[FK04a] Berndt Farwer and Michael Köhler. Mobile object-net systems and their processes. Fundamenta Informaticae, 60(1-4):113-129, 2004.

[FK04b] Berndt Farwer and Manfred Kudlek. A new synchronisation model for multi-level object petri nets. Fundamenta Informaticae, 60(1-4):131-142, 2004.

[FK05a] B. Farwer and M. Köhler. Modelling global and local namespaces for mobile agents using object nets. In Proceedings of Concurrency, Specification, and Programming CS&P’2005. University of Warsaw, 2005.

[FK05b] B. Farwer and S. Kohl. Object systems with process markings. In B. Farwer, editor, Object Petri Nets, Processes, and Object Calculi, pages 1–11. FBI-HH-B-265/05, Fachbereich Informatik, Universität Hamburg, 2005.

[FL03] B. Farwer and M. Leuschel. Model checking object Petri nets in Prolog. Technical Report DSSE-TR-2003-4, Declarative Systems and Software Engineering Group, School of Electronics and Computer Science, University of Southampton, SO17 1BJ, UK, 2003.

[FL04] B. Farwer and M. Leuschel. Model checking object Petri nets in Prolog. In Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming, pages 20–31. ACM Press, 2004.

[FM03] B. Farwer and K. Misra. Modelling with hierarchical object Petri nets. Fundamenta Informaticae, 55(2):129-147, 2003.

[FV05] B. Farwer and M. Varea. Object-based control/data-flow analysis. Technical Report DSSE-TR-2005-1, ECS, University of Southampton, 2005.

[Köh03] Michael Köhler. Object petri nets: Definitions, properties, and related models. Technical Report FBI-HH-M-329/03, Universität Hamburg, Fachbereich Informatik, 2003.

[KR04] M. Köhler and H. Rölke. Properties of object petri nets. In J. Cortadella and W. Reisig, editors, Applications And Theory of Petri Nets 2004, LNCS 3099, pages 278-297. Springer-Verlag, 2004.

[Kum00] O. Kummer. Undecidability in object-oriented Petri nets. Petri Net Newsletter, (59):18-23, 2000.

[Kum02] O. Kummer. Referenznetze. Logos Verlag, 2002.

[Lak94] C. A. Lakos. Object Petri nets - definition and relationship to coloured nets. Technical report, TR94-3, Computer Science Department, University of Tasmania, 1994.

[Lak95] C. A. Lakos. From coloured Petri nets to object Petri nets. In K. Jensen, editor, Application and Theory of Petri Nets, LNCS 935, pages 278-297. Springer-Verlag, 1995.

[Val95] R. Valk. Petri nets as dynamical objects. In Workshop Proc. of the 16th International Conference on Application and Theory of Petri Nets, Torino, Italy, 1995.

[Val96a] R. Valk. How to define markings in object systems. Petri Net Newsletter 50, 1996.

[Val96b] R. Valk. On processes of object Petri nets. Technical report, FBI-HH-B-185/96, Fachbereich Informatik, Universität Hamburg, 1996.

[Val98] R. Valk. Petri nets as token objects. An introduction to elementary object nets. In J. Desel and M. Silva, editors, Applications and Theory of Petri Nets 1998. Proceedings, volume 1420, pages 1-25. Springer-Verlag, 1998.

[Val99] R. Valk. Reference and value semantics for object Petri nets. In H. Weber, H. Ehrig, and W. Reisig, editors, Colloquium on Petri Net Technologies for Modelling Communication Based Systems, pages 169-188. Fraunhofer Institute for Software and Systems Engineering ISST, Berlin, 1999.

[Val00] R. Valk. Relating different semantics for object Petri nets. Technical report, FBI-HH-B-266/00, Fachbereich Informatik, Universität Hamburg, 2000.


© 2003-2006, Berndt Farwer