A Petri net (also known as a place/transition net or P/T net) is one of several mathematical representations of discrete distributed systems. As a modeling language, it graphically depicts the structure of a distributed system as a directed bipartite graph with annotations. As such, a Petri net has place nodes, transition nodes, and directed arcs connecting places with transitions. Petri nets were invented in 1962 by Carl Adam Petri in his PhD thesis. Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ... Knowledge representation is needed for library classification and for processing concepts in an information system. ... This article or section should include material from Distributed programming This article or section should include material from Distributed system Distributed computing is the process of aggregating the power of several computing entities to collaboratively run a single computational task in a transparent and coherent way, so that they appear... In computer science and allied fields of information management and business process modeling, modelling languages enable software architects, business analysts, and others to specify the requirements of an organizational or software system on a top or architectural level. ... In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets with two vertices of the same set never sharing an edge. ... Place is a term that has a variety of meanings in a dictionary sense, but which is principally used as a noun to denote location, though in a sense of a location identified with that which is located there. ... In telecommunication, a transition is the change from one signal state to another signal state. ... 1962 (MCMLXII) was a common year starting on Monday (link will take you to calendar). ... Carl Adam Petri is a honorary professor at the University of Hamburg. ...

At any one time during a Petri net's execution, each place can hold zero or more tokens. Unlike more traditional data processing systems that can process only a single stream of incoming tokens, Petri net transitions can consume tokens from multiple input places, act on them, and output tokens to multiple output places. Transition can only act on the tokens if the required number of tokens appear in every one of its input places. Token can mean one of several things: In computer science, specifically lexical analysis, a token is usually a word or an atomic element within a string. ...

Transitions act on input tokens by a process known as firing. When a transition fires, it consumes the tokens from its input places, performs some processing task, and places a specified number of tokens into each of its output places. It does this atomically, namely in one single non-preemptible step. Since firing is non-deterministic, Petri nets are well suited for modeling concurrent behavior of distributed systems. In the theory of computation, a nondeterministic algorithm is a hypothetical algorithm where computation can branch, choosing among different execution paths in a way that does not depend only on the input and current execution state. ... Parallel programming (also concurrent programming), is a computer programming technique that provides for the execution of operations concurrently, either within a single computer, or across a number of systems. ...

A Formal definition

Example Petri net

A Petri net is a tuple (S,T,F,M₀,W,K), where (see Desel and Juhás ^[1]) In mathematics, a tuple is a finite sequence of objects, that is, a list of a limited number of objects (an infinite sequence is a family). ...

• S is a set of places.
• T is a set of transitions.
• F is a set of arcs known as a flow relation. It is subject to the constraint that no arc connects two places or two transitions, or more formally: .
• known as an initial marking, where for each place , there are tokens.
• known as a set of arc weights, assigns to each arc some denoting how many tokens are consumed from a place by a transition, or alternatively, how many tokens are produced by a transition and put into each place.
• known as capacity restrictions, assigns to each place some positive number denoting the maximum number of tokens that can occupy that place.

A variety of other formal definitions exist. This definition is for a place-transition (or P-T) net. Most other definitions do not include arc weights or capacity restrictions.

Basic Petri nets

A Petri net consists of places, transitions and directed arcs. Arcs run between places and transitions - not between places and places or transitions and transitions. The input places of a transition are the places from which an arc runs to it; its output places are those to which an arc runs from it. Place is a term that has a variety of meanings in a dictionary sense, but which is principally used as a noun to denote location, though in a sense of a location identified with that which is located there. ... In telecommunication, a transition is the change from one signal state to another signal state. ... A diagram of a graph with 6 vertices and 7 edges. ...

Places may contain any number of tokens. A distribution of tokens over the places of a net is called a marking. Transitions can fire, that is, execute: when a transition fires, it consumes a token from each of its input places, and produces a token on each of its output places. A transition is enabled if it can fire, i.e., there are tokens in every input place. Token can mean one of several things: In computer science, specifically lexical analysis, a token is usually a word or an atomic element within a string. ... A marking might be: an annotation an animal marking, such as the spots of a leopard a road marking, such as lines or words, or the stripes of a Zebra crossing. ... It has been suggested that flame be merged into this article or section. ...

Execution of Petri nets is nondeterministic. This means two things: In the theory of computation, a nondeterministic algorithm is a hypothetical algorithm where computation can branch, choosing among different execution paths in a way that does not depend only on the input and current execution state. ...

1. multiple transitions can be enabled at the same time, any one of which can fire
2. none are required to fire - they fire at will, between time 0 and infinity, or not at all(!) i.e. it is totally possible that nothing fires at all.

Basic mathematical properties

The state of a Petri net is represented as an M vector, where the 1st value of the vector is the amount of tokens in the 1st place of the net, the 2nd is amount of tokens in the 2nd place, and so on. Such a representation fully describles the state of a Petri net.

A state-transition list, , which can be shortened to simply is called a firing sequence if each and every transition satisfies the firing criteria (i.e. there are enough tokens in the input for every transition). In this case, the state-transition list of is called a trajectory, and is called reachable from through the firing sequence of . Mathematically written: .

The state-transition matrix W ⁻ is | T | by | S | large, and represents the amount of tokens taken by each transition from each place. Similarly, W ⁺ represents the amount of tokens given by each transition to each place. The sum of the two, W = W ⁻ + W ⁻ can be used for calculating the above mentioned equation of which can now be simply written as , where σ is a vector of how many times each transition fired in the sequence. Note that just because the equation can be satisfied, does not mean that it can actually be carried out - for that there should be enough tokens for each transition to fire, i.e. the satisfiability of the equation is required but not sufficient to say that state M_n can be reached from state M₀.

The reachability of the states can be represented with a reachablitiy graph where a directed graph' points represent states (i.e. M), and arcs transitions between two such states. The graph is constructed as follows: the starting state (M₀) is then taken, and all possible transitions are explored, then the transitions from these states, and so on. The way the graph should be constructed is through breadth-first search (as the graph may be infinitely large, and so depth-first search would not find all possible states even if given inifinite time). In computer science, breadth-first search (BFS) is a tree search algorithm used for traversing or searching a tree, tree structure, or graph. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...

While reachability seems to a be a good tool to find erroneous states, such as an elevator moving while the door is open, the constructed graph has far too many states for practical problems. For these reasons, the LTL logic with tableau method is usually used to prove that such states can not be reached. Linear temporal logic (LTL) is a field of mathematical logic that is able to talk about the future of paths. ... Analytic tableaux, or, more briefly, just tableaux, are a fundamental concept in automated theorem proving. ...

Extensions

There are many extensions to Petri nets. Some of them are completely backwards-compatible (e.g. colored Petri nets) with the original Petri net, some add properties that can not be modelled in the original Petri net (e.g. timed Petri nets). If they can be modelled in the original Peti net, they are not real extensions, instead are convenient ways of showing the same thing, and can be transformed with mathematical formulas back to the original Petri net, without loosing any meaning. Extensions that can not be transfomed are sometimes very powerful, but usually lack the amount of mathematical tools available to analyse normal Petri nets.

The term high-level Petri net is used for many Petri net formalisms that extend the basic P/T net formalsism. This includes coloured Petri nets, hierarchical Petri nets, and all other extensions sketched in this section.

A short list of possible extensions:

• In a standard Petri net, tokens are indistinguishable. In a coloured Petri net, every token has a value. In popular tools for colored Petri nets such as CPN Tools, the values of tokens are typed, and can be tested and manipulated with a functional programming language. Firing of a transition in both standard and coloured Petri nets is fully determined by the presence of tokens in the input places.

• Another popular extension of Petri nets is hierarchy: Hierarchy in the form of different views supporting levels of refinement and abstraction were studied by Fehling. Another form of hierarchy is found in so-called object Petri nets or object systems where a Petri net can contain Petri nets as its tokens inducing a hierarchy of nested Petri nets that communicate by synchronisation of transitions on different levels. See [2] for an informal introduction to object Petri nets.

• Stochastic Petri nets add non-deterministic time.

• A Vector Addition System with States (VASS) can be seen as a generalization of a Petri net. Consider a finite state automaton where each transition is labeled by a transition from the Petri net. The Petri net is then synchronized with the finite state automaton, i.e., a transition in the automaton is taken at the same time as the corresponding transition in the Petri net. It is only possible to take a transition in the automaton if the corresponding transition in the Petri net is enabled, and it is only possible to fire a transition in the Petri net if there is a transition from the current state in the automaton labeled by it. (The definition of VASS is usually formulated slightly differently.)

• Prioritised Petri nets add priorities to transitions, whereby a transition can not fire, if a higher-priority transition is enabled (i.e. can fire). Thus, transitions are in priority groups, and e.g. priority group 3 can only fire if all transitions are disabled in groups 1 and 2. Within a priority group, firing is still non-deterministic.

• The non-deterministic property has been a very valueable one, as it lets the user abstract a large number of properties (depending on what the net is used for). In certain cases, however, the need arises to also model the timing, not only the structure of a model. For these cases, timed Petri nets have evolved, where there are transitions that are timed, and possibly transitions which are not timed (if there are, transitions that are not timed have a higher priority than timed ones). This way, the property of time can also be modelled (not only the structure).

There are many more extensions to Petri nets, however, it is important to keep in mind, that as the complexity of the net increases in terms of extended properties, the harder it is to use standard tools to evaluate certain properties of the net. For this reason, it is a good idea to use the most simple net type possible for a given modelling task. Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ... A hierarchy (in Greek: Ιεραρχία, it is derived from ιερός-hieros, sacred, and άρχω-arkho, rule) is a system of ranking and organizing things or people. ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ...

Petri net theory

The theoretical properties of Petri nets have been studied extensively.

A marking of a Petri net is reachable if, starting in the initial marking, a sequence of transition firings exists that produces it. A Petri net is bounded if there is a maximum to the number of tokens in its reachable markings. The term bounded appears in different parts of mathematics where a notion of size can be given. ...

Boundedness is decidable by looking at covering, by constructing the Karp-Miller Tree. Reachability is known to be decidable, however in at least exponential time. All known general algorithms so far, however, employ non-primitive recursive space. Further details may be found in this survey [3] and in Kurt Jensen Coloured Petri Nets, and in M. Ajmone Marsan et al. Modelling with Generalized Stochastic Petri Nets. In combinatorics and computer science, the covering problem is a type of general question: if a certain structure covers another, or how many structures are required to cover another? For Petri nets, for example, the covering problem is defined as the question if for a given marking, there exists a... Richard M. Karp (born 1935) is a computer scientist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985. ... In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ...

Main Petri net types

Petri net types graphically

There are six main types of petri net:

1. State Machine (SM) - here, every transition has one incoming arc, and one outgoing arc. This means, that there can not be concurrency, but there can be conflict (i.e. Where should the token from the place go? To one transition or the other?). Mathematically:
2. Marked Graph (MG) - here, every place has one incoming arc, and one outgoing arc. This means, that there can not be conflict, but there can be concurrency. Mathematically:
3. Free choice (FC) - here, an arc is either the only arc going from the place, or it is the only arc going to a transition. I.e. there can be both concurrency and conflict, but not at the same time. Mathematically:
4. Extended free choice (EFC) - a Petri net that can be transformed into an FC.
5. Assymetric choice (AC) - concurrecy and conflict (in sum, confusion), but not assymetrically.Mathematically:
6. Petri Net (PN) - confusion is allowed (i.e. everything is allowed)

In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ...

Subsequent models of concurrency

Subsequent to the invention of Petri nets other models of concurrency, which are based on message passing and feature compositionality (e.g. the Actor model and the various process calculi), have been introduced. Robin Milner and Carl Hewitt have argued that the lack of compositionality is a serious limitation of Petri nets because the deficiency limits modularity. In computer science, Message passing is used in concurrent programming, parallel programming, and object-oriented programming, to accomplish communication by sending messages to recipients. ... The Principle of Compositionality in semantics is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. ... In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation. ... The Process calculi (or process algebras) are a diverse family of related approaches to formally modelling concurrent systems. ... Robin Milner is a prominent British computer scientist. ... Carl Hewitt is a US scientist who is an emeritus professor from MIT. He is known for his design of Planner that was the first Artificial Intelligence programming language based on procedural plans that were invoked using pattern-directed invocation from assertions and goals. ... Modularity is a concept that has applications in the contexts of computer science, particularly programming, as well as cognitive science in investigating the structure of mind. ...

In addition, Hewitt has argued that Petri nets lack locality because input tokens of a transition disappear simultaneously, which limits the realism of the model. He acknowledged the counterargument that the proper use of Petri nets is to obey the single event restriction which is that every transition should model a single event. An example of such a transition would be one with two input places, one representing the month being September 2005, and the other representing the date being September 30, 2005. If the event being modeled were the passing of midnight on that day, obviously both tokens would disappear at the same time. However obeying the single event restriction drastically limits the applications of Petri nets. Realism is commonly defined as a concern for fact or reality and rejection of the impractical and visionary. ...

Application areas

• Software design
• Workflow management
• Data analysis
• Concurrent programming
• Reliability engineering
• Diagnosis for finding the original error in the line of error -> error state -> visible error

Software engineering (SE) is the profession concerned with specifying, designing, developing and maintaining software applications by applying technologies and practices from computer science, project management, and other fields. ... Workflow is the operational aspect of a work procedure: how tasks are structured, who performs them, what their relative order is, how they are synchronized, how information flows to support the tasks and how tasks are being tracked. ... Data Analysis Data analysis is the means by which the Information Systems auditor determines the completeness and accuracy of an organization’s data. ... Parallel programming (also concurrent programming), is a computer programming technique that provides for the execution of operations concurrently, either within a single computer, or across a number of systems. ... It has been suggested that Reliability (engineering) be merged into this article or section. ... Diagnosis (from the Greek words dia = by and gnosis = knowledge) is the process of identifying a disease by its signs, symptoms and results of various diagnostic procedures. ...

Programming tools

See the list of Petri net tools. The following is a list of Petri net tools. ...

See also

• Finite state machine
• Vector Addition System with States (VASS)

It has been suggested that this article or section be merged with Deterministic finite state machine. ...

References

• Cardoso, Janette, Heloisa Camargo. Fuzziness in Petri Nets, Physica-Verlag. ISBN 3-7908-1158-0.
• ^ Desel, Jörg and Juhás, Gabriel "What Is a Petri Net? -- Informal Answers for the Informed Reader", Hartmut Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001.
• Jensen, Kurt. Coloured Petri Nets, Springer Verlag. ISBN 3-540-62867-3.
• Peterson, James Lyle. Petri Net Theory and the Modeling of Systems, Prentice Hall. ISBN 0136619835.
• Reisig, Wolfgang. A Primer in Petri Net Design, Springer-Verlag. ISBN 3-540-52044-9.
• Riemann, Robert-Christoph. Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus, Herbert Utz Verlag. ISBN 3-89675-629-X.
• Störrle, Harald. Models of Software Architecture - Design and Analysis with UML and Petri-Nets, Books on Demand. ISBN 3-8311-1330-0.
• Zhou, Mengchu, Frank Dicesare. Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer Academic Publishers. ISBN 0792392892.
• Zhou, Mengchu. Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach, World Scientific Publishing. ISBN 981023029X.

External links

• Petri Nets World
• Petri Net Markup Language
• exchangeable Routing Language
• Citations from CiteSeer