Petri net

Petri net
User:Msoos · CC BY-SA 2.5 · source
Name	Petri net
Invented by	Carl Adam Petri
Year	1962
Field	Computer science; Systems theory
Related	Place/transition net; Workflow net; Timed Petri net

Petri net A Petri net is a mathematical modeling language for the description and analysis of distributed systems. It provides a graphical and formal framework combining places, transitions, and tokens to represent concurrent, asynchronous, nondeterministic, and parallel processes. Petri nets are used across Computer science, Systems theory, Electrical engineering, Operations research, Biology, and Business process modeling.

Definition and basic concepts

A Petri net model comprises places, transitions, and directed arcs connecting them, with tokens residing in places to represent system state; changing token distributions through transition firings models system dynamics. Core notions include marking, firing rule, enabling condition, reachability, and boundedness, which relate to system properties like liveness and safety. Key practitioners and institutions that advanced these concepts include Carl Adam Petri, Edsger W. Dijkstra, Conrad L. Heitmeyer, Jens Palsberg, University of Bonn, Massachusetts Institute of Technology, Technische Universität Berlin, and École Polytechnique. Foundational works were disseminated at venues such as ACM SIGPLAN, IFIP, IEEE, International Conference on Concurrency Theory, and International Workshop on Petri Nets.

Formal definitions and mathematical properties

Formally, a Petri net is a bipartite directed multigraph (P, T, F) with a marking M: P → ℕ; firing semantics define state transitions producing reachability graphs and incidence matrices. Mathematical properties studied include reachability, boundedness, conservativeness, persistence, reversibility, and structural properties such as invariants (place and transition invariants). Important theoretical tools and contributors include John Hopcroft, Robert Tarjan, Edsger W. Dijkstra (concurrency foundations), Stephen Cook, Richard Karp, Michael Rabin, Dana Scott, Robin Milner, Tony Hoare, Leslie Lamport, Amir Pnueli, Jifeng He, Moshe Vardi, Edmund Clarke, E. Allen Emerson, Jukka-Pekka Tolvanen, and institutions like Stanford University, University of Cambridge, Princeton University, University of California, Berkeley, and University of Oxford. Decision problems for Petri nets connect to complexity classes studied by Juraj Hromkovič, Leslie Valiant, Leonid Levin, and Alan Turing-era computability research.

Types and extensions

Numerous variants extend the basic model to capture timing, hierarchy, stochastic behavior, priorities, colors, and resources. Major types include place/transition nets, colored Petri nets, timed Petri nets, stochastic Petri nets, high-level Petri nets, interpreter nets, colored stochastic nets, workflow nets, and hybrid Petri nets. Researchers and groups exploring these include Klaus Jensen, Günter Reisig, Wil van der Aalst, Marlon Dumas, Jan Mendling, Antoni Mazurkiewicz, Jörg Desel, Winfried Reisig, Rolf Reijers, Heinz Koenig, Paul Leach, and centers such as Eindhoven University of Technology, University of Twente, RWTH Aachen University, Technical University of Denmark, and Imperial College London.

Analysis techniques and tools

Analysis methods include reachability graph generation, coverability trees, invariant analysis, linear algebraic methods, model checking, state-space reduction, unfoldings, structural analysis, and performance evaluation via stochastic simulation. Verification and toolchains often integrate with model checkers and theorem provers developed by teams from Microsoft Research, Bell Labs, IBM Research, Google Research, University of Warwick, University of Illinois Urbana–Champaign, Carnegie Mellon University, ETH Zurich, University of Tokyo, and Nanyang Technological University. Prominent tools and frameworks include CPN Tools, PIPE, Tina, GreatSPN, WoPeD, Renew, Snoopy, and accompanying research at conferences like International Conference on Tools and Algorithms for the Construction and Analysis of Systems, International Symposium on Formal Methods, and International Workshop on Petri Nets and Performance Models.

Applications and examples

Petri nets model communication protocols, distributed algorithms, manufacturing systems, workflow management, biochemical networks, and embedded controllers. Representative application domains and case studies have been presented in contexts such as Internet Engineering Task Force standards validation, European Space Agency mission planning, Siemens industrial control, General Electric power systems, Bosch automotive controllers, Toyota manufacturing, Boeing avionics, Philips medical devices, Pfizer drug development pipelines, and Centers for Disease Control and Prevention epidemiological models. Example models include the dining philosophers problem (studied by Edsger W. Dijkstra and Tony Hoare), mutual exclusion protocols analyzed at MIT, pipeline processors examined at Intel Corporation, and signal processing pipelines modeled for Nokia and Ericsson telecommunications.

History and development

The concept originated with Carl Adam Petri in the early 1960s, with formal publication in his doctoral work and subsequent dissemination through symposiums and journals. Development accelerated with contributions from Klaus Jensen on colored nets, Günter Reisig on semantics, and Wil van der Aalst on workflow applications, supported by institutions like University of Hamburg, University of Amsterdam, University of Erlangen–Nuremberg, Universidade de São Paulo, and University of Illinois. The field matured through international collaborations and workshops sponsored by organizations such as IFIP, ACM, IEEE Computer Society, European Research Council, and national research agencies including Deutsche Forschungsgemeinschaft and National Science Foundation. Evolution of the theory influenced formal methods, concurrency theory, and systems engineering across academia and industry.

Category:Petri nets