|
|
| Line 1: |
Line 1: |
| A '''Petri net''' (also known as a '''place/transition net''' or '''P/T net''') is one of several [[mathematical]] [[modeling language]]s for the description of [[distributed systems]]. A Petri net is a directed [[bipartite graph]], in which the nodes represent transitions (i.e. events that may occur, signified by bars) and places (i.e. conditions, signified by circles). The directed arcs describe which places are pre- and/or postconditions for which transitions (signified by arrows). Some sources<ref>Carl Adam Petri and Wolfgang Reisig (2008) Petri net. ''Scholarpedia'', 3(4):6477
| | In [[arithmetic]], an [[Odd number|odd]] [[composite number|composite]] [[integer]] ''n'' is called an '''Euler pseudoprime''' to base ''a'', if ''a'' and ''n'' are [[coprime]], and |
| [http://www.scholarpedia.org/article/Petri_net]</ref> 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.
| |
|
| |
|
| Like industry standards such as [[Unified Modeling Language|UML]] [[activity diagram]]s, [[BPMN]] and [[Event-driven process chain|EPC]]s, Petri nets offer a [[diagram|graphical notation]] for stepwise processes that include choice, [[iteration]], and [[Concurrent computing|concurrent execution]].
| | : <math>a^{(n-1)/2} \equiv \pm 1\pmod{n}</math> |
| Unlike these standards, Petri nets have an exact mathematical definition of their execution semantics, with a well-developed mathematical theory for process analysis.
| |
|
| |
|
| [[Image:Animated Petri net commons.gif|thumb|right|299px|(a) Petri net trajectory example]] | | (where ''mod'' refers to the [[modular arithmetic|modulo]] operation). |
|
| |
|
| == Petri net basics == | | The motivation for this definition is the fact that all [[prime number]]s ''p'' satisfy the above equation which can be deduced from [[Fermat's little theorem]]. Fermat's theorem asserts that if ''p'' is prime, and coprime to ''a'', then ''a''<sup>''p''−1</sup> = 1 (mod ''p''). Suppose that ''p''>2 is prime, then ''p'' can be expressed as 2''q'' + 1 where ''q'' is an integer. Thus; ''a''<sup>(2''q''+1) − 1</sup> = 1 (mod ''p'') which means that ''a''<sup>2''q''</sup> − 1 = 0 (mod ''p''). This can be factored as (''a''<sup>''q''</sup> − 1)(''a''<sup>''q''</sup> + 1) = 0 (mod ''p'') which is equivalent to ''a''<sup>(''p''−1)/2</sup> = ±1 (mod ''p''). |
| A Petri net consists of ''places'', ''transitions'', and ''[[graph theory|arc]]s''. 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.
| | The equation can be tested rather quickly, which can be used for probabilistic [[prime testing|primality testing]]. These tests are twice as strong as tests based on Fermat's little theorem. |
|
| |
|
| Unless an ''execution policy'' is defined, the execution of Petri nets is [[Nondeterministic algorithm|nondeterministic]]: when multiple transitions are enabled at the same time, any one of them may fire.
| | Every Euler pseudoprime is also a Fermat [[pseudoprime]]. It is not possible to produce a definite test of primality based on whether a [[number]] is an Euler pseudoprime because there exist ''absolute Euler pseudoprimes'', numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a [[subset]] of the absolute Fermat pseudoprimes, or [[Carmichael number]]s, and the smallest absolute Euler pseudoprime is [[1729 (number)|1729]] = 7×13×19. |
|
| |
|
| 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 [[Concurrency (computer science)|concurrent]] behavior of distributed systems.
| | The stronger condition that ''a''<sup>(''n''−1)/2</sup> = (''a''/''n'') (mod ''n''), where (''a'',''n'') = 1 and (''a''/''n'') is the [[Jacobi symbol]], is sometimes used for a definition of an Euler pseudoprime. A discussion of numbers of this form can be found at [[Euler–Jacobi pseudoprime]]. |
|
| |
|
| == Formal definition and basic terminology == | | ==See also== |
| Petri nets are [[State transition system|state-transition systems]] that extend a class of nets called elementary nets.<ref>G. Rozenburg, J. Engelfriet, Elementary Net Systems, in: W. Reisig, G. Rozenberg (Eds.), Lectures on Petri Nets I: Basic Models - Advances in Petri Nets, volume 1491 of Lecture Notes in Computer Science, Springer,1998, pp. 12-121.</ref>
| | * [[Probable prime]] |
|
| |
|
| '''Definition 1.''' A ''net'' is a triple <math>N = (P, T, F)</math> where:
| | ==References== |
| # <math>P</math> and <math>T</math> are ''disjoint'' finite sets of ''places'' and ''transitions'', respectively.
| |
| # <math>F \subset (P \times T) \cup (T \times P)</math> is a set of ''arcs'' (or flow relations).
| |
|
| |
|
| | *N. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987. |
| | *H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985. |
|
| |
|
| '''Definition 2.''' Given a net ''N'' = (''P'', ''T'', ''F'' ), a ''configuration'' is a set ''C'' so that ''C'' <big>⊆</big> ''P''.
| | {{DEFAULTSORT:Euler Pseudoprime}} |
| | [[Category:Pseudoprimes]] |
|
| |
|
| [[File:Petri Net A.jpg|thumb|A Petri net with an enabled transition.]][[File:Petri Net B.jpg|thumb|The Petri net that follows after the transition fires (Initial Petri net in the figure above).]] | | [[de:Eulersche Pseudoprimzahl]] |
| '''Definition 3.''' An ''elementary net'' is a net of the form ''EN'' = (''N'', ''C'' ) where:
| | [[fr:Nombre pseudopremier d'Euler]] |
| # ''N'' = (''P'', ''T'', ''F'' ) is a net.
| | [[it:Pseudoprimo di Eulero]] |
| # ''C'' is such that ''C'' <big>⊆</big> ''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'' <big>→</big> ''Z'' is a place [[multiset]], where ''Z'' is a countable set. ''M'' extends the concept of ''configuration'' and is commonly described with reference to Petri net diagrams as a ''marking''.
| |
| # ''W'' : ''F'' <big>→</big> ''Z'' is an arc [[multiset]], 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 {0,1} 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]] ''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<sub>1</sub>'' is an input place of transition ''t''; whereas, the place ''p<sub>2</sub>'' is an output place to the same transition. Let ''PN<sub>0</sub>'' (Fig. top) be a Petri net with a marking configured ''M<sub>0</sub>'' and ''PN<sub>1</sub>'' (Fig. bottom) be a Petri net with a marking configured ''M<sub>1</sub>''. The configuration of ''PN<sub>0</sub>'' ''enable'' 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<sub>1</sub>'' in the image of ''M<sub>0</sub>'' and results in Petri net ''PN<sub>1</sub>'', 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 (see<ref>Wolfgang Reisig: Petri Nets and Algebraic Specifications. Theoretical Computer Science 80(1): 1-34 (1991)</ref>).
| |
| | |
| The following formal definition is loosely based on {{harv|Peterson|1981}}. Many alternative definitions exist.
| |
| | |
| === Syntax ===
| |
| | |
| A '''Petri net graph''' (called ''Petri net'' by some, but see below) is a 3-[[tuple]] <math>(S,T,W)\!</math>, where
| |
| * ''S'' is a [[finite set]] of ''places''
| |
| * ''T'' is a finite set of ''transitions''
| |
| * ''S'' and ''T'' are [[Disjoint sets|disjoint]], i.e. no object can be both a place and a transition
| |
| * <math>W: (S \times T) \cup (T \times S) \to \mathbb{N}</math> is a [[multiset]] of [[directed edge|arc]]s, 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: <math> F = \{ (x,y) \mid W(x,y) > 0 \}</math>. 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 graph|bipartite]] [[multigraph]] <math>(S \cup T, F)</math> with node partitions ''S'' and ''T''.
| |
| | |
| The ''preset'' of a transition ''t'' is the set of its ''input places'': <math>{}^{\bullet}t = \{ s \in S \mid W(s,t) > 0 \}</math>;
| |
| its ''postset'' is the set of its ''output places'': <math>t^{\bullet} = \{ s \in S \mid W(t,s) > 0 \}</math>. 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 <math>M: S \to \mathbb{N}</math>. 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 <math>(S,T,W,M_0)\!</math>, where
| |
| * <math>(S,T,W)</math> is a Petri net graph;
| |
| * <math>M_0</math> is the ''initial marking'', a marking of the Petri net graph.
| |
| | |
| === Execution semantics ===
| |
| | |
| | |
| | |
| In words:
| |
| * firing a transition ''t'' in a marking ''M'' consumes <math>W(s,t)</math> tokens from each of its input places ''s'', and produces <math>W(t,s)</math> tokens in each of its output places ''s''
| |
| * a transition is ''enabled'' (it may ''fire'') in ''M'' if there are enough tokens in its input places for the consumptions to be possible, i.e. iff <math>\forall s: M(s) \geq W(s,t)</math>.
| |
| | |
| We are generally interested in what may happen when transitions may continually fire in arbitrary order.
| |
| | |
| We say that a marking <math>M'</math> ''is reachable from'' a marking ''M'' ''in one step'' if <math>M \to_G M'</math>; we say that it ''is reachable from'' ''M'' if <math>M {\to_G}^* M'</math>, where <math>{\to_G}^*</math> is the [[reflexive transitive closure]] of <math>\to_G</math>; that is, if it is reachable in 0 or more steps.
| |
| | |
| For a (marked) Petri net <math>N=(S,T,W,M_0)\!</math>, we are interested in the firings that can be performed starting with the initial marking <math>M_0</math>. Its set of ''reachable markings'' is the set
| |
| <math>R(N) \ \stackrel{D}{=}\ \{ M' \mid M_0 {\to_{(S,T,W)}}^* M' \} </math>
| |
| | |
| The ''reachability graph'' of ''N'' is the transition relation <math>\to_G</math> restricted to its reachable markings <math>R(N)</math>. It is the [[state space]] of the net.
| |
| | |
| A ''firing sequence'' for a Petri net with graph ''G'' and initial marking <math>M_0</math> is a sequence of transitions <math>\vec \sigma = \langle t_{i_1} \ldots t_{i_n} \rangle</math> such that <math>M_0 \to_{G,t_{i_1}} M_1 \wedge \ldots \wedge M_{n-1} \to_{G,t_{i_n}} M_n</math>. The set of firing sequences is denoted as <math>L(N)</math>.
| |
| | |
| == Variations on the definition ==
| |
| | |
| As already remarked, a common variation is to disallow arc multiplicities and replace the [[multiset|bag]] of arcs ''W'' with a simple set, called the ''flow relation'', <math>F \subseteq (S \times T) \cup (T \times S)</math>.
| |
| This doesn't limit [[expressive power]] as both can represent each other.
| |
| | |
| Another common variation, e.g. in, Desel and Juhás (2001),<ref>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. [http://www.springerlink.com/content/a6lmwqye66ll5w56/]</ref> 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 <math>(S,T,W,M_0)\!</math> can be regarded as [[Vector (mathematics)|vector]]s of nonnegative integers of length <math>|S|</math>.
| |
| | |
| Its transition relation can be described as a pair of <math>|S|</math> by <math>|T|</math> [[matrix (mathematics)|matrices]]:
| |
| * <math>W^-</math>, defined by <math>\forall s,t: W^-[s,t] = W(s,t)</math>
| |
| * <math>W^+</math>, defined by <math>\forall s,t: W^+[s,t] = W(t,s).</math>
| |
| Then their difference
| |
| * <math> W^T = W^+ - W^-</math>
| |
| can be used to describe the reachable markings in terms of matrix multiplication, as follows.
| |
| For any sequence of transitions ''w'', write <math>o(w)</math> for the vector that maps every transition to its number of occurrences in ''w''. Then, we have
| |
| * <math>R(N) = \{ M \mid \exists w: M = M_0 + W^T \cdot o(w) \wedge w \!</math> is a firing sequence of <math>N \}\!</math>.<!-- the \!s make the \{ and \} the same size. -->
| |
| | |
| Note that it must be required that ''w'' is a firing sequence; allowing arbitrary sequences of transitions will generally produce a larger set.
| |
| | |
| [[Image:detailed petri net.png|frame|(b) Petri net Example]] <math>W^{+}=\begin{bmatrix} * & t1 & t2 \\ p1 & 0 & 1 \\ p2 & 1 & 0 \\ p3 & 1& 0 \\ p4 & 0 & 1 \end{bmatrix} </math>
| |
| | |
| <math> W^{-}=\begin{bmatrix} * & t1 & t2 \\ p1 & 1 & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \end{bmatrix} </math>
| |
| | |
| <math>W^T=\begin{bmatrix} * & t1 & t2 \\ p1 & -1 & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \end{bmatrix}</math>
| |
| | |
| <math>M_{0}=\begin{bmatrix} 1 & 0 & 2 & 1 \end{bmatrix}</math>
| |
| | |
| == 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]]s, with decidability and complexity results for Petri nets and some subclasses, can be found in
| |
| Esparza and Nielsen (1995).<ref>[http://citeseer.ist.psu.edu/226920.html ''Decidability issues for Petri nets - a survey'', by Javier Esparza and Mogens Nielsen, in: ''Bulletin of the EATCS'', 1994. Revised, 1995.]</ref>
| |
| | |
| === Reachability ===
| |
| The [[reachability problem]] for Petri nets is to decide, given a Petri net ''N'' and a marking ''M'', whether <math>M \in R(N)</math>.
| |
| | |
| Clearly, this is a matter of walking the reachability graph defined above, until either we reach the requested marking or we know it can no longer be found. This is harder than it may seem at first: the reachability graph is generally infinite, and it is not easy to determine when it is safe to stop.
| |
| | |
| In fact, this problem was shown to be [[EXPSPACE]]-hard<ref>Lipton, R. [http://citeseer.ist.psu.edu/contextsummary/115623/0 "The Reachability Problem Requires Exponential Space"], Technical Report 62, Yale University, 1976]</ref> years before it was shown to be decidable at all (Mayr, 1981). Papers continue to be published on how to do it efficiently.<ref>P. Küngas. [http://www.idi.ntnu.no/%7Epeep/papers/SARA2005Kung.ps Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies]. In: ''Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation'', SARA 2005, Airth Castle, Scotland, UK, July 26–29, 2005]</ref>
| |
| | |
| 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 [[Method of analytic tableaux|tableau method]] to prove that such states cannot be reached. LTL uses the [[semi-decision procedure|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 ===
| |
| | |
| [[Image:liveness-levels.gif|thumb|right|A Petri net in which transition <math>t_0</math> is dead, and <math>{}_{\forall j>0: t_j}</math> is <math>L_j</math>-live]]
| |
| | |
| Petri nets can be described as having different degrees of liveness <math>L_1 - L_4</math>. A Petri net <math>(N, M_0)</math> is called <math>L_k</math>-live [[if and only if|iff]] all of its transitions are <math>L_k</math>-live, where a transition is
| |
| * ''dead'', iff it can never fire, i.e. it is not in any firing sequence in <math>L(N,M_0)</math>
| |
| * <math>L_1</math>-live (''potentially fireable''), iff it may fire, i.e. it is in some firing sequence in <math>L(N,M_0)</math>
| |
| * <math>L_2</math>-live iff it can fire arbitrarily often, i.e. if for every positive integer k, it occurs at least k times in some firing sequence in <math>L(N,M_0)</math>
| |
| * <math>L_3</math>-live iff it can fire infinitely often, i.e. if for every positive integer k, it occurs at least k times in ''V'', for some prefix-closed set of firing sequences <math>{}_{V \subseteq L(N,M_0)}</math>
| |
| * <math>L_4</math>-live (''live'') iff it may always fire, i.e., it is <math>L_1</math>-live in every reachable marking in <math>R(N,M_0)</math>
| |
| | |
| Note that these are increasingly stringent requirements: <math>L_{j+1}</math>-liveness implies <math>L_j</math>-liveness, for <math>{}_{j \in {1,2,3}}</math>.
| |
| | |
| These definitions are in accordance with Murata's overview,<ref>''Petri Nets: Properties, Analysis and Applications'', by Tadao Murata, in: ''Proceedings of the IEEE'', vol. 77, no. 4, April 1989 (see [http://www.cs.uic.edu/~murata/publications.html])</ref> which additionally uses <math>L_0</math>''-live'' as a term for ''dead''.
| |
| | |
| === Boundedness ===
| |
| | |
| [[File:Reachability graph for petri net.png|right|frame|width=50px|The reachability graph of ''N2''.]]
| |
| | |
| A place in Petri net is called ''k-bounded'' 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 set|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.
| |
| | |
| Note that a Petri net is bounded if and only if its reachability graph is finite.
| |
| | |
| Boundedness is decidable by looking at [[covering problem|covering]], by constructing the [[Richard Karp|Karp]]–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.<ref>
| |
| {{Cite web
| |
| |url=http://www.techfak.uni-bielefeld.de/~mchen/BioPNML/Intro/pnfaq.html
| |
| |ref=harv
| |
| |title=Petri Nets
| |
| |postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}
| |
| }}
| |
| </ref>
| |
| Formally, ''Petri nets with place capacities'' can be defined as tuples <math>(S,T,W,C,M_0)</math>, where <math>(S,T,W,M_0)</math> is a Petri net, <math>C: P \rightarrow\!\!\!\shortmid I\!N</math> 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.
| |
| | |
| [[File:Two-boundedness-ub.png|left|frame|An unbounded Petri net, ''N''.]]
| |
| | |
| 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.
| |
| | |
| [[File:Two-boundedness-cb.png|left|frame|A two-bounded Petri net, obtained by extending ''N'' with "counter-places".]]
| |
| | |
| 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 discrete events, there are Petri nets for continuous and hybrid discrete-continuous processes and useful in discrete, continuous and hybrid [[control theory]].<ref>[http://books.google.com/books?id=VsS0JkMcXGwC Discrete, continuous, and hybrid Petri Nets], René David, Hassane Alla, Springer, 2005, ISBN 978-3-540-22480-8</ref> and related to discrete, continuous and hybrid [[automata theory|automata]].
| |
| | |
| ==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 (e.g. timed Petri nets). If they can be modelled in the original Petri net, they are not real extensions, instead, they are convenient ways of showing the same thing, and can be transformed with mathematical formulas back to the original Petri net, without losing any meaning. Extensions that cannot be transformed are sometimes very powerful, but usually lack the full range 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 formalism; this includes coloured Petri nets, hierarchical Petri 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]].
| |
| | |
| A short list of possible extensions:
| |
| | |
| *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,<ref>T. Araki and T. Kasami, ''Some Decision Problems Related to the Reachability Problem for Petri Nets'', in: ''Theoretical Computer Science'', 3(1), pp. 85-104 (1977)</ref> while some other properties, such as termination, remain decidable;<ref>C. Dufourd, A. Finkel, and Ph. Schnoebelen: ''Reset Nets Between Decidability and Undecidability'', in: ''Proceedings of the 25th International Colloquium on Automata, Languages and Programming'', [[Lecture Notes in Computer Science|LNCS]] vol. 1443, pp. 103-115 (1998)</ref>
| |
| **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]] and implies existence of a universal net.<ref>[http://daze.ho.ua Zaitsev D.A.] Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12, http://dx.doi.org/10.1109/TSMC.2012.2237549</ref>
| |
| *In a standard Petri net, tokens are indistinguishable. In a [[Coloured Petri net]], every token has a value.<ref>[http://www.daimi.au.dk/CPnets/intro/verybrief.html "Very Brief Introduction to CP-nets"], Department of Computer Science, University of Aarhus, Denmark</ref> In popular tools for coloured Petri nets such as [[CPN Tools]], the values of tokens are typed, and can be tested (using ''guard'' expressions) and manipulated with a [[functional programming language]]. A subsidiary of coloured Petri nets are the [[well-formed Petri net]]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<ref>http://llpn.com/OPNs.html</ref> for an informal introduction to object Petri nets.
| |
| | |
| *A [[Vector Addition System with States (VASS)]] can be seen as a generalisation of a Petri net. Consider a [[finite state automaton]] 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 net]]s 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 net]]s that add [[nondeterministic time]] through adjustable randomness of the transitions. The [[Exponential distribution|exponential random distribution]] is usually used to 'time' these nets. In this case, the nets' reachability graph can be used as a [[Markov chain]].
| |
| | |
| *[[Dualistic Petri Nets]] (dP-Nets) is a Petri Net extension developed by E. Dawis, et al.<ref>Dawis, E. P., J. F. Dawis, Wei-Pin Koo (2001). Architecture of Computer-based Systems using Dualistic Petri Nets. Systems, Man, and Cybernetics, 2001 IEEE International Conference on Volume 3, 2001 Page(s):1554 - 1558 vol.3</ref> 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]]. 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,<ref>Dawis, E. P. (2001). Architecture of an SS7 Protocol Stack on a Broadband Switch Platform using Dualistic Petri Nets. Communications, Computers and signal Processing, 2001. PACRIM. 2001 IEEE Pacific Rim Conference on Volume 1, 2001 Page(s):323 - 326 vol.1</ref> where development requirements are organized around the structure of the designed system. dP-Nets allow any real-world process, such as computer systems, business processes, traffic flow, etc., to be modeled, studied, and improved.
| |
| | |
| 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:
| |
| [[Image:petri net types.svg|thumb|right|299px|Petri net types graphically]]
| |
| # 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]]{{dn|date=September 2013}}). Mathematically: <math>\forall t\in T: |t^\bullet|=|{}^\bullet t|=1</math>
| |
| # 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: <math>\forall s\in S: |s^\bullet|=|{}^\bullet s|=1</math>
| |
| # 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: <math>\forall s\in S: (|s^\bullet|\leq 1) \vee ({}^\bullet (s^\bullet)=\{s\})</math>
| |
| # 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''. Mathematically: <math>\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>
| |
| <!-- the next definition needs to be cleaned up by someone who understands what is meant here
| |
| # In a ''multiple asymmetric choice'' net (MAC), multiple concurrency and conflict (in sum, ''multiple confusion'') may occur, but no ''confusion''. Mathematically: ''for a set |P|=k,'' <math>\forall t\in T </math> exist a subset <math> {}^\bullet t,</math> and <math> {}^\bullet T </math> contains all subsets and is the powerset 2<sup>''k''</sup> without the empty subset
| |
| -->
| |
| | |
| ==Other models of concurrency==
| |
| | |
| Other ways of modelling concurrent computation have been proposed, including [[process algebra]], the [[actor model]], and [[trace theory]].<ref>Antoni Mazurkiewicz, "Introduction to Trace Theory", in ''The Book of Traces'' V. Diekert, G. Rozenberg, eds. World Scientific, Singapore (1995) pp 3-67.</ref> Different models provide tradeoffs of concepts such as [[compositionality]], [[Modularity (programming)|modularity]], and locality.
| |
| | |
| An approach to relating some of these models of concurrency is proposed in the chapter by Winskel and Nielsen.<ref>G. Winskel, M. Nielsen. [http://www.daimi.au.dk/PB/463/PB-463.pdf "Models for Concurrency"]. Handbook of Logic and the Foundations of Computer Science, vol. 4, pages 1-148, OUP.</ref>
| |
| | |
| == Application areas ==
| |
| | |
| * [[Software design]]
| |
| * [[Workflow management]]
| |
| * [[Process Modeling]]
| |
| * [[Data analysis]]
| |
| * [[Concurrent programming]]
| |
| * [[Reliability engineering]]
| |
| * [[Diagnosis (Artificial intelligence)|Diagnosis]]
| |
| * [[Sequential function chart|Discrete process control]]
| |
| * [[Simulation]]
| |
| * [[Kahn process networks|KPN modeling]]
| |
| | |
| == See also ==
| |
| * [[Communicating finite-state machine]]
| |
| * [[Finite state machine]]
| |
| * [[Kahn process networks]]
| |
| * [[Petri Net Markup Language]]
| |
| * [[Petriscript]]
| |
| * [[Process architecture]]
| |
| | |
| == References ==
| |
| {{reflist|30em}}
| |
| | |
| == Further reading ==
| |
| *{{cite book
| |
| | last = Cardoso
| |
| | first = Janette
| |
| | authorlink =
| |
| | coauthors = Heloisa Camargo
| |
| | year =1999
| |
| | title = Fuzziness in Petri Nets
| |
| | publisher = Physica-Verlag
| |
| | isbn = 3-7908-1158-0}}
| |
| *{{cite book
| |
| | last = Jensen
| |
| | first = Kurt
| |
| | authorlink =
| |
| | year =1997
| |
| | title = Coloured Petri Nets
| |
| | publisher = Springer Verlag
| |
| | isbn = 3-540-62867-3}}
| |
| *{{cite book
| |
| | last = Котов
| |
| | first = Вадим
| |
| | authorlink =
| |
| | year = 1984
| |
| | title = Сети Петри (Petri Nets, in Russian)
| |
| | publisher = Наука, Москва
| |
| | id = }}
| |
| *{{cite book
| |
| | last = Pataricza
| |
| | first = András
| |
| | authorlink =
| |
| | year = 2004
| |
| | title = Formális módszerek az informatikában (Formal methods in informatics)
| |
| | publisher = TYPOTEX Kiadó
| |
| | isbn = 963-9548-08-1}}
| |
| *{{cite journal
| |
| | last =Peterson
| |
| | first = James L.
| |
| | author =
| |
| | title=Petri Nets
| |
| | journal=ACM Computing Surveys
| |
| | year=1977
| |
| | volume=9
| |
| | issue=3
| |
| | pages=223–252
| |
| | url=
| |
| | doi =10.1145/356698.356702
| |
| | ref =harv }}
| |
| <!-- note: {{cite book}} doesn't work with the {{harv}} reference above; {{Citation}} does -->
| |
| *{{Cite document
| |
| | last = Peterson
| |
| | first = James Lyle
| |
| | authorlink =
| |
| | year = 1981
| |
| | title = Petri Net Theory and the Modeling of Systems
| |
| | publisher = Prentice Hall
| |
| | ref = harv
| |
| | postscript = <!--None-->
| |
| | isbn = 0-13-661983-5}}
| |
| *{{Cite journal
| |
| | author=Petri, Carl A.
| |
| | title=Kommunikation mit Automaten
| |
| | publisher=University of Bonn
| |
| | year=1962
| |
| | version=Ph. D. Thesis
| |
| | url=
| |
| | accessdate= }}
| |
| *{{cite web
| |
| | last = Petri
| |
| | first = Carl Adam
| |
| | last2 = Reisig
| |
| | first2 = Wolfgang
| |
| | authorlink =
| |
| | title = Petri net
| |
| | work = Scholarpedia 3(4):6477
| |
| | url = http://www.scholarpedia.org/article/Petri_net
| |
| | accessdate = 2008-07-13}}
| |
| *{{cite book
| |
| | last = Reisig
| |
| | first = Wolfgang
| |
| | authorlink =
| |
| | year =1992
| |
| | title = A Primer in Petri Net Design
| |
| | publisher = Springer-Verlag
| |
| | isbn = 3-540-52044-9}}
| |
| *{{cite book
| |
| | last = Riemann
| |
| | first = Robert-Christoph
| |
| | authorlink =
| |
| | year =1999
| |
| | title = Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus
| |
| | publisher = Herbert Utz Verlag
| |
| | isbn = 3-89675-629-X}}
| |
| *{{cite book
| |
| | last = Störrle
| |
| | first = Harald
| |
| | authorlink =
| |
| | year =2000
| |
| | title = Models of Software Architecture - Design and Analysis with UML and Petri-Nets
| |
| | publisher = Books on Demand
| |
| | isbn = 3-8311-1330-0}} <span style="color:gray;">With courtesy of the author, freely available [http://www.pst.informatik.uni-muenchen.de/~stoerrle/V/Dissertation.pdf online].</span>
| |
| *{{cite book
| |
| | last = Zhou
| |
| | first = Mengchu
| |
| | authorlink = | coauthors = Frank Dicesare
| |
| | year =1993
| |
| | title = Petri Net Synthesis for Discrete Event Control of Manufacturing Systems
| |
| | publisher = Kluwer Academic Publishers
| |
| | isbn = 0-7923-9289-2}}
| |
| *{{cite book
| |
| | last = Zhou
| |
| | first = Mengchu
| |
| | authorlink =
| |
| | coauthors = Kurapati Venkatesh
| |
| | year =1998
| |
| | title = Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach
| |
| | publisher = World Scientific Publishing
| |
| | isbn = 981-02-3029-X}}
| |
| *{{cite book
| |
| | last = Zaitsev
| |
| | first = Dmitry
| |
| | authorlink =
| |
| | year = 2013
| |
| | title = Clans of Petri Nets: Verification of protocols and performance evaluation of networks
| |
| | publisher = LAP LAMBERT Academic Publishing
| |
| | isbn = 978-3-659-42228-7
| |
| | url = https://www.morebooks.de/store/gb/book/clans-of-petri-nets/isbn/978-3-659-42228-7}}
| |
| | |
| == External links ==
| |
| {{commons category|Petri nets}}
| |
| * [http://www.informatik.uni-hamburg.de/TGI/PetriNets/ Petri Nets World]
| |
| * [http://www.pnml.org Petri Net Markup Language]
| |
| * [http://code.google.com/p/jbpt/ Java implementation of Petri nets] in the jBPT library (see jbpt-petri module)
| |
| * [http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/java/Braunl/ Java Petri net simulator]
| |
| * [http://people.dsv.su.se/~petia/WorkflowTutorial/player.html Petia Wohed's Flash-based tutorial introduction to Workflow Technology with Petri Nets]
| |
| *[http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/quick.html List of Petri net tools]
| |
| | |
| {{DEFAULTSORT:Petri Net}}
| |
| [[Category:Formal specification languages]]
| |
| [[Category:Models of computation]]
| |
| [[Category:Concurrency (computer science)]]
| |
| [[Category:Diagrams]]
| |
| [[Category:Petri nets| ]]
| |
| [[Category:Software modeling language]]
| |