HOME

TheInfoList



OR:

A Petri net, also known as a place/transition (PT) net, is one of several
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
modeling language A modeling language is any artificial language that can be used to express information or knowledge or systems in a structure that is defined by a consistent set of rules. The rules are used for interpretation of the meaning of components in th ...
s for the description of
distributed systems A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
. It is a class of
discrete event dynamic system In control engineering, a discrete-event dynamic system (DEDS) is a discrete-state, event-driven system of which the state evolution depends entirely on the occurrence of asynchronous discrete events over time. Although similar to continuous-variab ...
. A Petri net is a directed bipartite graph that has two types of elements, places and transitions. Place elements are depicted as white circles and transition elements are depicted as rectangles. A place can contain any number of tokens, depicted as black circles. A transition is enabled if all places connected to it as inputs contain at least one token. Some sources state that Petri nets were invented in August 1939 by
Carl Adam Petri Carl Adam Petri (12 July 1926 in Leipzig – 2 July 2010 in Siegburg) was a German mathematician and computer scientist. Life and work Petri created his major scientific contribution, the concept of the Petri net, in 1939 at the age of 13, for ...
—at the age of 13—for the purpose of describing chemical processes. Like industry standards such as
UML The Unified Modeling Language (UML) is a general-purpose, developmental modeling language in the field of software engineering that is intended to provide a standard way to visualize the design of a system. The creation of UML was originally m ...
activity diagram 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 o ...
s,
Business Process Model and Notation Business Process Model and Notation (BPMN) is a graphical representation for specifying business processes in a business process model. Originally developed by the Business Process Management Initiative (BPMI), BPMN has been maintained by the Ob ...
, and
event-driven process chain An event-driven process chain (EPC) is a type of flow chart for business process modeling. EPC can be used to configure enterprise resource planning execution, and for business process improvement. It can be used to control an autonomous workflow ...
s, Petri nets offer a graphical notation for stepwise processes that include choice,
iteration Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
, and concurrent execution. Unlike these standards, Petri nets have an exact mathematical definition of their execution semantics, with a well-developed mathematical theory for process analysis.


Historical background

The German computer scientist
Carl Adam Petri Carl Adam Petri (12 July 1926 in Leipzig – 2 July 2010 in Siegburg) was a German mathematician and computer scientist. Life and work Petri created his major scientific contribution, the concept of the Petri net, in 1939 at the age of 13, for ...
, for whom such structures are named, analyzed Petri nets extensively in his 1962 dissertation .


Petri net basics

A Petri net consists of ''places'', ''transitions'', and '' arcs''. Arcs run from a place to a transition or vice versa, never between places or between transitions. The places from which an arc runs to a transition are called the ''input places'' of the transition; the places to which arcs run from a transition are called the ''output places'' of the transition. Graphically, places in a Petri net may contain a discrete number of marks called ''tokens''. Any distribution of tokens over the places will represent a configuration of the net called a ''marking''. In an abstract sense relating to a Petri net diagram, a transition of a Petri net may ''fire'' if it is ''enabled'', i.e. there are sufficient tokens in all of its input places; when the transition fires, it consumes the required input tokens, and creates tokens in its output places. A firing is atomic, i.e. a single non-interruptible step. Unless an ''execution policy'' (e.g. a strict ordering of transitions, describing precedence) is defined, the execution of Petri nets is nondeterministic: when multiple transitions are enabled at the same time, they will fire in any order. Since firing is nondeterministic, and multiple tokens may be present anywhere in the net (even in the same place), Petri nets are well suited for modeling the
concurrent Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to: Law * Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea'' * Concurring opinion (also called a "concurrence"), a ...
behavior of distributed systems.


Formal definition and basic terminology

Petri nets are state-transition systems that extend a class of nets called elementary nets. Definition 1. A ''net'' is a
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
N = (P, T, F) where # P and T are disjoint finite sets of ''places'' and ''transitions'', respectively. # F \subseteq (P \times T) \cup (T \times P) is a set of (directed) ''arcs'' (or flow relations). Definition 2. Given a net ''N'' = (''P'', ''T'', ''F''), a ''configuration'' is a set ''C'' so that ''C'' ''P''. Definition 3. An ''elementary net'' is a net of the form ''EN'' = (''N'', ''C'') where # ''N'' = (''P'', ''T'', ''F'') is a net. # ''C'' is such that ''C'' ''P'' is a ''configuration''. Definition 4. A ''Petri net'' is a net of the form ''PN'' = (''N'', ''M'', ''W''), which extends the elementary net so that # ''N'' = (''P'', ''T'', ''F'') is a net. # ''M'' : ''P'' ''Z'' is a place
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
, where ''Z'' is a
countable set In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
. ''M'' extends the concept of ''configuration'' and is commonly described with reference to Petri net diagrams as a ''marking''. # ''W'' : ''F'' ''Z'' is an arc
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
, so that the count (or weight) for each arc is a measure of the arc ''multiplicity''. If a Petri net is equivalent to an elementary net, then ''Z'' can be the countable set and those elements in ''P'' that map to 1 under ''M'' form a configuration. Similarly, if a Petri net is not an elementary net, then the
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
''M'' can be interpreted as representing a non-singleton set of configurations. In this respect, ''M'' extends the concept of configuration for elementary nets to Petri nets. In the diagram of a Petri net (see top figure right), places are conventionally depicted with circles, transitions with long narrow rectangles and arcs as one-way arrows that show connections of places to transitions or transitions to places. If the diagram were of an elementary net, then those places in a configuration would be conventionally depicted as circles, where each circle encompasses a single dot called a ''token''. In the given diagram of a Petri net (see right), the place circles may encompass more than one token to show the number of times a place appears in a configuration. The configuration of tokens distributed over an entire Petri net diagram is called a ''marking''. In the top figure (see right), the place ''p''1 is an input place of transition ''t''; whereas, the place ''p''2 is an output place to the same transition. Let ''PN''0 (top figure) be a Petri net with a marking configured ''M''0, and ''PN''1 (bottom figure) be a Petri net with a marking configured ''M''1. The configuration of ''PN''0 ''enables'' transition ''t'' through the property that all input places have sufficient number of tokens (shown in the figures as dots) "equal to or greater" than the multiplicities on their respective arcs to ''t''. Once and only once a transition is enabled will the transition fire. In this example, the ''firing'' of transition ''t'' generates a map that has the marking configured ''M''1 in the image of ''M''0 and results in Petri net ''PN''1, seen in the bottom figure. In the diagram, the firing rule for a transition can be characterised by subtracting a number of tokens from its input places equal to the multiplicity of the respective input arcs and accumulating a new number of tokens at the output places equal to the multiplicity of the respective output arcs. Remark 1. The precise meaning of "equal to or greater" will depend on the precise algebraic properties of addition being applied on ''Z'' in the firing rule, where subtle variations on the algebraic properties can lead to other classes of Petri nets; for example, algebraic Petri nets. The following formal definition is loosely based on . Many alternative definitions exist.


Syntax

A Petri net graph (called ''Petri net'' by some, but see below) is a 3-
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
(S,T,W), where * ''S'' is a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...
of ''places'' * ''T'' is a finite set of ''transitions'' * ''S'' and ''T'' are disjoint, i.e. no object can be both a place and a transition * W: (S \times T) \cup (T \times S) \to \mathbb is a
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
of arcs, i.e. it assigns to each arc a non-negative integer ''arc multiplicity'' (or weight); note that no arc may connect two places or two transitions. The ''flow relation'' is the set of arcs: F = \. In many textbooks, arcs can only have multiplicity 1. These texts often define Petri nets using ''F'' instead of ''W''. When using this convention, a Petri net graph is a bipartite
multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...
(S \cup T, F) with node partitions ''S'' and ''T''. The ''preset'' of a transition ''t'' is the set of its ''input places'': ^t = \; its ''postset'' is the set of its ''output places'': t^ = \. Definitions of pre- and postsets of places are analogous. A ''marking'' of a Petri net (graph) is a multiset of its places, i.e., a mapping M: S \to \mathbb. We say the marking assigns to each place a number of ''tokens''. A Petri net (called ''marked Petri net'' by some, see above) is a 4-tuple (S,T,W,M_0), where * (S,T,W) is a Petri net graph; * M_0 is the ''initial marking'', a marking of the Petri net graph.


Execution semantics

In words * firing a transition in a marking consumes W(s,t) tokens from each of its input places , and produces W(t,s) tokens in each of its output places * a transition is ''enabled'' (it may ''fire'') in if there are enough tokens in its input places for the consumptions to be possible, i.e. if and only if \forall s: M(s) \geq W(s,t). We are generally interested in what may happen when transitions may continually fire in arbitrary order. We say that a marking ''is reachable from'' a marking ''in one step'' if M \underset M'; we say that it ''is reachable from '' if M \overset M', where \overset is the
reflexive transitive closure In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but ...
of \underset; that is, if it is reachable in 0 or more steps. For a (marked) Petri net N=(S,T,W,M_0), we are interested in the firings that can be performed starting with the initial marking M_0. Its set of ''reachable markings'' is the set R(N) \ \stackrel\ \left\ The ''reachability graph'' of is the transition relation \underset restricted to its reachable markings R(N). It is the
state space A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the toy ...
of the net. A ''firing sequence'' for a Petri net with graph and initial marking M_0 is a sequence of transitions \vec \sigma = \langle t_ \cdots t_ \rangle such that M_0 \underset M_1 \wedge \cdots \wedge M_ \underset M_n. The set of firing sequences is denoted as L(N).


Variations on the definition

A common variation is to disallow arc multiplicities and replace the bag of arcs ''W'' with a simple set, called the ''flow relation'', F \subseteq (S \times T) \cup (T \times S). This does not limit expressive power as both can represent each other. Another common variation, e.g. in Desel and Juhás (2001), is to allow ''capacities'' to be defined on places. This is discussed under ''extensions'' below.


Formulation in terms of vectors and matrices

The markings of a Petri net (S,T,W,M_0) can be regarded as
vector Vector most often refers to: *Euclidean vector, a quantity with a magnitude and a direction *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematic ...
s of non-negative integers of length , S, . Its transition relation can be described as a pair of , S, by , T,
matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
: * W^-, defined by \forall s,t: W^- ,t= W(s,t) * W^+, defined by \forall s,t: W^+ ,t= W(t,s). Then their difference * W^T = - W^- + W^+ can be used to describe the reachable markings in terms of matrix multiplication, as follows. For any sequence of transitions , write o(w) for the vector that maps every transition to its number of occurrences in . Then, we have * R(N) = \. It must be required that is a firing sequence; allowing arbitrary sequences of transitions will generally produce a larger set. W^=\begin * & t1 & t2 \\ p1 & 1 & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \end, \ W^=\begin * & t1 & t2 \\ p1 & 0 & 1 \\ p2 & 1 & 0 \\ p3 & 1& 0 \\ p4 & 0 & 1 \end, \ W^T=\begin * & t1 & t2 \\ p1 & -1 & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \end M_=\begin 1 & 0 & 2 & 1 \end


Category-theoretic formulation

Meseguer and Montanari considered a kind of symmetric monoidal categories known as Petri categories.


Mathematical properties of Petri nets

One thing that makes Petri nets interesting is that they provide a balance between modeling power and analyzability: many things one would like to know about concurrent systems can be automatically determined for Petri nets, although some of those things are very expensive to determine in the general case. Several subclasses of Petri nets have been studied that can still model interesting classes of concurrent systems, while these problems become easier. An overview of such
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
s, with decidability and complexity results for Petri nets and some subclasses, can be found in Esparza and Nielsen (1995).


Reachability

The
reachability problem Reachability is a fundamental problem that appears in several different contexts: finite- and infinite-state concurrent systems, computational models like cellular automata and Petri nets, program analysis, discrete and continuous systems, time c ...
for Petri nets is to decide, given a Petri net ''N'' and a marking ''M'', whether M \in R(N). It is a matter of walking the reachability-graph defined above, until either the requested-marking is reached or it can no longer be found. This is harder than it may seem at first: the reachability graph is generally infinite, and it isn't easy to determine when it is safe to stop. In fact, this problem was shown to be EXPSPACE-hard years before it was shown to be decidable at all (Mayr, 1981). Papers continue to be published on how to do it efficiently. In 2018, Czerwiński et al. improved the lower bound and showed that the problem is not
ELEMENTARY Elementary may refer to: Arts, entertainment, and media Music * ''Elementary'' (Cindy Morgan album), 2001 * ''Elementary'' (The End album), 2007 * ''Elementary'', a Melvin "Wah-Wah Watson" Ragin album, 1977 Other uses in arts, entertainment, a ...
. In 2021, this problem was shown to be non-primitive recursive, independently by Jerome Leroux and by Wojciech Czerwiński and Łukasz Orlikowski. These results thus close the long-standing complexity gap. While reachability seems to be a good tool to find erroneous states, for practical problems the constructed graph usually has far too many states to calculate. To alleviate this problem, linear temporal logic is usually used in conjunction with the tableau method to prove that such states cannot be reached. Linear temporal logic uses the semi-decision technique to find if indeed a state can be reached, by finding a set of necessary conditions for the state to be reached then proving that those conditions cannot be satisfied.


Liveness

Petri nets can be described as having different degrees of liveness L_1 - L_4. A Petri net (N, M_0) is called L_k-live
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is b ...
all of its transitions are L_k-live, where a transition is * ''dead'', if it can never fire, i.e. it is not in any firing sequence in L(N,M_0) * L_1-live (''potentially fireable''), if and only if it may fire, i.e. it is in some firing sequence in L(N,M_0) * L_2-live if it can fire arbitrarily often, i.e. if for every positive integer , it occurs at least times in some firing sequence in L(N,M_0) * L_3-live if it can fire infinitely often, i.e. if there is some fixed (necessarily infinite) firing sequence in which for every positive integer , the transition L_3 occurs at least times, * L_4-live (''live'') if it may always fire, i.e. it is L_1-live in every reachable marking in R(N,M_0) Note that these are increasingly stringent requirements: L_-liveness implies L_j-liveness, for \textstyle. These definitions are in accordance with Murata's overview, which additionally uses L_0''-live'' as a term for ''dead''.


Boundedness

A place in a Petri net is called ''k-bound'' if it does not contain more than ''k'' tokens in all reachable markings, including the initial marking; it is said to be ''safe'' if it is 1-bounded; it is '' bounded'' if it is ''k-bounded'' for some ''k''. A (marked) Petri net is called ''k''-bounded, ''safe'', or ''bounded'' when all of its places are. A Petri net (graph) is called ''(structurally) bounded'' if it is bounded for every possible initial marking. A Petri net is bounded if and only if its reachability graph is finite. Boundedness is decidable by looking at covering, by constructing the
Karp Karp may refer to: Places * Karp, Podlaskie Voivodeship, in north-east Poland * Karp, Lublin Voivodeship, in east Poland People * Karp (surname) * Karp Khachvankyan (1923–1998), Armenian actor and director Other uses * KARP-FM, a radio s ...
–Miller Tree. It can be useful to explicitly impose a bound on places in a given net. This can be used to model limited system resources. Some definitions of Petri nets explicitly allow this as a syntactic feature. Formally, ''Petri nets with place capacities'' can be defined as tuples (S,T,W,C,M_0), where (S,T,W,M_0) is a Petri net, C: P \rightarrow\!\!\!\shortmid \mathbb N an assignment of capacities to (some or all) places, and the transition relation is the usual one restricted to the markings in which each place with a capacity has at most that many tokens. For example, if in the net ''N'', both places are assigned capacity 2, we obtain a Petri net with place capacities, say ''N2''; its reachability graph is displayed on the right. Alternatively, places can be made bounded by extending the net. To be exact, a place can be made ''k''-bounded by adding a "counter-place" with flow opposite to that of the place, and adding tokens to make the total in both places ''k''.


Discrete, continuous, and hybrid Petri nets

As well as for discrete events, there are Petri nets for continuous and hybrid discrete-continuous processes that are useful in discrete, continuous and hybrid
control theory Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...
, and related to discrete, continuous and hybrid
automata An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
.


Extensions

There are many extensions to Petri nets. Some of them are completely backwards-compatible (e.g. coloured Petri nets) with the original Petri net, some add properties that cannot be modelled in the original Petri net formalism (e.g. timed Petri nets). Although backwards-compatible models do not extend the computational power of Petri nets, they may have more succinct representations and may be more convenient for modeling. Extensions that cannot be transformed into Petri nets are sometimes very powerful, but usually lack the full range of mathematical tools available to analyse ordinary Petri nets. The term high-level Petri net is used for many Petri net formalisms that extend the basic P/T net formalism; this includes coloured Petri nets, hierarchical Petri nets such as Nets within Nets, and all other extensions sketched in this section. The term is also used specifically for the type of coloured nets supported by
CPN Tools CPN Tools is a tool for editing, simulating, and analyzing high-level Petri nets. It supports basic Petri nets plus timed Petri nets and colored Petri nets. It has a simulator and a state space analysis tool is included. CPN Tools is originally dev ...
. A short list of possible extensions follows: * Additional types of arcs; two common types are ** a ''reset arc'' does not impose a precondition on firing, and empties the place when the transition fires; this makes reachability undecidable, while some other properties, such as termination, remain decidable; ** an ''inhibitor arc'' imposes the precondition that the transition may only fire when the place is empty; this allows arbitrary computations on numbers of tokens to be expressed, which makes the formalism
Turing complete Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
and implies existence of a universal net. * In a standard Petri net, tokens are indistinguishable. In a
coloured Petri net Coloured Petri nets are a backward compatible extension of the mathematical concept of 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. ...
, every token has a value. In popular tools for coloured Petri nets such as
CPN Tools CPN Tools is a tool for editing, simulating, and analyzing high-level Petri nets. It supports basic Petri nets plus timed Petri nets and colored Petri nets. It has a simulator and a state space analysis tool is included. CPN Tools is originally dev ...
, the values of tokens are typed, and can be tested (using ''guard'' expressions) and manipulated with a
functional programming language In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
. A subsidiary of coloured Petri nets are the
well-formed Petri net Well-formed Petri nets are a Petri net class jointly elaborated between the University of Paris 6 (Université P. & M. Curie) and the University of Torino in the early 1990s. It is a restriction of the high-level nets (or colored Nets) introduced b ...
s, where the arc and guard expressions are restricted to make it easier to analyse the net. * Another popular extension of Petri nets is hierarchy; this in the form of different views supporting levels of refinement and abstraction was 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 for an informal introduction to object Petri nets. * A vector addition system with states (VASS) is an equivalent formalism to Petri nets. However, it can be superficially viewed as a generalisation of Petri nets. Consider a
finite state automaton A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
where each transition is labelled by a transition from the Petri net. The Petri net is then synchronised 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 labelled by it. (The definition of VASS is usually formulated slightly differently.) * Prioritised Petri nets add priorities to transitions, whereby a transition cannot 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 valuable 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). A subsidiary of timed Petri nets are the stochastic Petri nets that add nondeterministic time through adjustable randomness of the transitions. The exponential random distribution is usually used to 'time' these nets. In this case, the nets' reachability graph can be used as a continuous time Markov chain (CTMC). * Dualistic Petri Nets (dP-Nets) is a Petri Net extension developed by E. Dawis, et al. to better represent real-world process. dP-Nets balance the duality of change/no-change, action/passivity, (transformation) time/space, etc., between the bipartite Petri Net constructs of transformation and place resulting in the unique characteristic of ''transformation marking'', i.e., when the transformation is "working" it is marked. This allows for the transformation to fire (or be marked) multiple times representing the real-world behavior of process throughput. Marking of the transformation assumes that transformation time must be greater than zero. A zero transformation time used in many typical Petri Nets may be mathematically appealing but impractical in representing real-world processes. dP-Nets also exploit the power of Petri Nets' hierarchical abstraction to depict
Process architecture Process architecture is the structural design of general process systems. It applies to fields such as computers (software, hardware, networks, etc.), business processes ( enterprise architecture, policy and procedures, logistics, project managemen ...
. Complex process systems are modeled as a series of simpler nets interconnected through various levels of hierarchical abstraction. The process architecture of a packet switch is demonstrated in, where development requirements are organized around the structure of the designed system. 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.


Restrictions

Instead of extending the Petri net formalism, we can also look at restricting it, and look at particular types of Petri nets, obtained by restricting the syntax in a particular way. Ordinary Petri nets are the nets where all arc weights are 1. Restricting further, the following types of ordinary Petri nets are commonly used and studied: # In a state machine (SM), every transition has one incoming arc, and one outgoing arc, and all markings have exactly one token. As a consequence, there can ''not'' be ''concurrency'', but there can be ''conflict'' (i.e.
nondeterminism Nondeterminism or nondeterministic may refer to: Computer science *Nondeterministic programming *Nondeterministic algorithm *Nondeterministic model of computation **Nondeterministic finite automaton **Nondeterministic Turing machine *Indeterminacy ...
): mathematically, \forall t\in T: , t^\bullet, =, ^\bullet t, =1 # In a marked graph (MG), every place has one incoming arc, and one outgoing arc. This means, that there can ''not'' be ''conflict'', but there can be ''concurrency:'' mathematically, \forall s\in S: , s^\bullet, =, ^\bullet s, =1 # In a ''free choice'' net (FC), every arc from a place to a transition is either the only arc from that place or the only arc to that transition, i.e. there can be ''both concurrency and conflict, but not at the same time'': mathematically, \forall s\in S: (, s^\bullet, \leq 1) \vee (^\bullet (s^\bullet)=\) # Extended free choice (EFC) – a Petri net that can be ''transformed into an FC''. # In an ''asymmetric choice'' net (AC), concurrency and conflict (in sum, ''confusion'') may occur, but ''not symmetrically: m''athematically, \forall s_1,s_2\in S: (s_1^\bullet \cap s_2^\bullet\neq \emptyset) \to s_1^\bullet\subseteq s_2^\bullet) \vee (s_2^\bullet\subseteq s_1^\bullet)/math>


Workflow nets

Workflow nets (WF-nets) are a subclass of Petri nets intending to model the
workflow A workflow consists of an orchestrated and repeatable pattern of activity, enabled by the systematic organization of resources into processes that transform materials, provide services, or process information. It can be depicted as a sequence o ...
of process activities. The WF-net transitions are assigned to tasks or activities, and places are assigned to the pre/post conditions. The WF-nets have additional structural and operational requirements, mainly the addition of a single input (source) place with no previous transitions, and output place (sink) with no following transitions. Accordingly, start and termination markings can be defined that represent the process status. WF-nets have the soundness property, indicating that a process with a start marking of ''k'' tokens in its source place, can reach the termination state marking with ''k'' tokens in its sink place (defined as ''k''-sound WF-net). Additionally, all the transitions in the process could fire (i.e., for each transition there is a reachable state in which the transition is enabled). A general sound (G-sound) WF-net is defined as being ''k''-sound for every ''k'' > 0. A directed
path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire p ...
in the Petri net is defined as the sequence of nodes (places and transitions) linked by the directed arcs. An elementary path includes every node in the sequence only once. A well-handled Petri net is a net in which there are no fully distinct elementary paths between a place and a transition (or transition and a place), i.e., if there are two paths between the pair of nodes then these paths share a node. An acyclic well-handled WF-net is sound (G-sound). Extended WF-net is a Petri net that is composed of a WF-net with additional transition t (feedback transition). The sink place is connected as the input place of transition t and the source place as its output place. Firing of the transition causes iteration of the process (Note, the extended WF-net is not a WF-net). WRI (Well-handled with Regular Iteration) WF-net, is an extended acyclic well-handled WF-net. WRI-WF-net can be built as composition of nets, i.e., replacing a transition within a WRI-WF-net with a subnet which is a WRI-WF-net. The result is also WRI-WF-net. WRI-WF-nets are G-sound, therefore by using only WRI-WF-net building blocks, one can get WF-nets that are G-sound by construction. The Design structure matrix (DSM) can model process relations, and be utilized for process planning. The DSM-nets are realization of DSM-based plans into workflow processes by Petri nets, and are equivalent to WRI-WF-nets. The DSM-net construction process ensures the soundness property of the resulting net.


Other models of concurrency

Other ways of modelling concurrent computation have been proposed, including vector addition systems, communicating finite-state machines,
Kahn process networks A Kahn process network (KPN, or process network) is a distributed ''model of computation'' in which a group of deterministic sequential processes communicate through unbounded first in, first out channels. The model requires that reading from a c ...
,
process algebra In computer science, the process calculi (or process algebras) are a diverse family of related approaches for formally modelling concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, and ...
, the actor model, and
trace theory In mathematics and computer science, trace theory aims to provide a concrete mathematical underpinning for the study of concurrent computation and process calculi. The underpinning is provided by an abstract algebra, algebraic definition of the fr ...
. Different models provide tradeoffs of concepts such as
compositionality In semantics, mathematical logic and related disciplines, the principle of compositionality 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. ...
, modularity, and locality. An approach to relating some of these models of concurrency is proposed in the chapter by Winskel and Nielsen.


Application areas

*
Boolean differential calculus Boolean differential calculus (BDC) (German: (BDK)) is a subject field of Boolean algebra discussing changes of Boolean variables and Boolean functions. Boolean differential calculus concepts are analogous to those of classical differential cal ...
(8 pages) *
Business process modeling Business process modeling (BPM) in business process management and systems engineering is the activity of process modeling, representing processes of an enterprise, so that the current business processes may be analyzed, improved, and automated. B ...
* Computational biology *
Concurrent programming Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to: Law * Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea'' * Concurring opinion (also called a "concurrence"), ...
*
Control engineering Control engineering or control systems engineering is an engineering discipline that deals with control systems, applying control theory to design equipment and systems with desired behaviors in control environments. The discipline of controls o ...
*
Data analysis Data analysis is a process of inspecting, cleansing, transforming, and modeling data with the goal of discovering useful information, informing conclusions, and supporting decision-making. Data analysis has multiple facets and approaches, enco ...
*
Diagnosis (artificial intelligence) As a subfield in artificial intelligence, Diagnosis is concerned with the development of algorithms and techniques that are able to determine whether the behaviour of a system is correct. If the system is not functioning correctly, the algorithm s ...
* Discrete process control *
Game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
*
Hardware design Processor design is a subfield of computer engineering and electronics engineering (fabrication) that deals with creating a processor, a key component of computer hardware. The design process involves choosing an instruction set and a certain exec ...
*
Kahn process networks A Kahn process network (KPN, or process network) is a distributed ''model of computation'' in which a group of deterministic sequential processes communicate through unbounded first in, first out channels. The model requires that reading from a c ...
*
Process modeling The term process model is used in various contexts. For example, in business process modeling the enterprise process model is often referred to as the ''business process model''. Overview Process models are processes of the same nature that a ...
* Reliability engineering *
Simulation A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of Conceptual model, models; the model represents the key characteristics or behaviors of the selected system or proc ...
* Software design *
Workflow management system A workflow management system (WfMS or WFMS) provides an infrastructure for the set-up, performance and monitoring of a defined sequence of tasks, arranged as a workflow application. International standards There are several international standards ...
s


See also

*
Finite-state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
* Petri Net Markup Language * Petriscript *
Process architecture Process architecture is the structural design of general process systems. It applies to fields such as computers (software, hardware, networks, etc.), business processes ( enterprise architecture, policy and procedures, logistics, project managemen ...
* Vector addition systems *
Machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...


References


Further reading

* * * * * * * * * * * * * * * {{DEFAULTSORT:Petri Net Formal specification languages Models of computation Concurrency (computer science) Diagrams Software modeling language Modeling languages