GetWiki
Petri net
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
Petri net
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{Short description|Model to describe distributed systems}}{{Use dmy dates|date=May 2019|cs1-dates=y}}A Petri net, also known as a place/transition net (PT net), is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. 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 sourcesJOURNAL, Carl Adam, Petri, Wolfgang, Reisig, 2008, Petri net, Scholarpedia, 3, 4, 6477, 10.4249/scholarpedia.6477, 2008SchpJ...3.6477P, free, 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 UML activity diagrams, Business Process Model and Notation, and event-driven process chains, Petri nets offer a graphical notation for stepwise processes that include choice, 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{{Citation needed|date=November 2020}}.- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
missing image!
- Animated Petri net commons.gif -
(a) Petri net trajectory example
- Animated Petri net commons.gif -
(a) Petri net trajectory example
Historical background
The German computer scientist Carl Adam Petri, after 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 behavior of distributed systems.Formal definition and basic terminology
Petri nets are state-transition systems that extend a class of nets called elementary nets.BOOK, G., Rozenburg, J., Engelfriet, Elementary Net Systems, W., Reisig, G., Rozenberg, Lectures on Petri Nets I: Basic Models â Advances in Petri Nets, 1491, Lecture Notes in Computer Science, Springer, 1998, 12â121, 3-540-65306-6, 10.1007/3-540-65306-6_14, Definition 1. A net is a tuple 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).
- N = (P, T, F) is a net.
- C is such that C â P is a configuration.
- N = (P, T, F) is a net.
- M : P â 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 â Z is an arc multiset, so that the count (or weight) for each arc is a measure of the arc multiplicity.
Syntax
A Petri net graph (called Petri net by some, but see below) is a 3-tuple (S,T,W), where- S is a finite set 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{N} is a multiset 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.
- (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 {{mvar|t}} in a marking {{mvar|M}} consumes W(s,t) tokens from each of its input places {{mvar|s}}, and produces W(t,s) tokens in each of its output places {{mvar|s}}
- a transition is enabled (it may fire) in {{mvar|M}} 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).
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),BOOK, Desel, Jörg, Juhás, Gabriel, What Is a Petri Net? Informal Answers for the Informed Reader, Hartmut, Ehrig, Hartmut Ehrig, Unifying Petri Nets, LNCS, 2128, 1â25, 2001, Springer, 10.1007/3-540-45541-8_1, etal, 9783540430674, 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 vectors of non-negative integers of length |S|.missing image!
- detailed petri net.png -
frame|(b) Petri net example
Its transition relation can be described as a pair of |S| by |T| matrices: - detailed petri net.png -
frame|(b) Petri net example
- W^-, defined by forall s,t: W^-[s,t] = W(s,t)
- W^+, defined by forall s,t: W^+[s,t] = W(t,s).
- W^T = - W^- + W^+
- R(N) = { M mid exists w: w text{ is a firing sequence of } N text{ and } M = M_0 + W^T cdot o(w) }.
Category-theoretic formulation
{{Expand section|date=September 2022}}Meseguer and Montanari considered a kind of symmetric monoidal categories known as Petri categories.JOURNAL, Petri nets are monoidslast1 = Meseguer | last2 = Montanari, Information and Computation, 88, 2, 105â155, October 1990, 10.1016/0890-5401(90)90013-8, Mathematical properties of Petri netsOne 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 determinations become easier.An overview of such decision problems, with decidability and complexity results for Petri nets and some subclasses, can be found in Esparza and Nielsen (1995).JOURNAL,citeseer.ist.psu.edu/226920.html, Decidability issues for Petri nets â a survey, Javier, Esparza, Mogens, Nielsen, Bulletin of the EATCS, 1994, Revised, 1995, 2014-05-14,ReachabilityThe reachability problem 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-hardJOURNAL, Lipton, R., Richard Lipton,citeseer.ist.psu.edu/contextsummary/115623/0, The Reachability Problem Requires Exponential Space, Technical Report 62, 1976, Yale University, 305â329, years before it was shown to be decidable at all (Mayr, 1981). Papers continue to be published on how to do it efficiently.CONFERENCE, P., Küngas,www.idi.ntnu.no/%7Epeep/papers/SARA2005Kung.ps, Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies, Proceedings of the 6th International Symposium on Abstraction, Reformulation and ApproximationâSARA 2005, Airth Castle, Scotland, UK, July 26â29, 2005, 10 July 2008,www.idi.ntnu.no/%7Epeep/papers/SARA2005Kung.ps," title="web.archive.org/web/20120209084910www.idi.ntnu.no/%7Epeep/papers/SARA2005Kung.ps,">web.archive.org/web/20120209084910www.idi.ntnu.no/%7Epeep/papers/SARA2005Kung.ps, 9 February 2012, dead, 3-540-31882-8, Lecture notes in computer science, 3607, Springer, 10.1007/11527862_11, 149â164, In 2018, CzerwiÅski et al. improved the lower bound and showed that the problem is not ELEMENTARY.ARXIV, 1809.07115, CzerwiÅski, Wojciech, The Reachability Problem for Petri Nets is Not Elementary (Extended Abstract), Lasota, SÅawomir, Lazic, Ranko, Leroux, Jerome, Mazowiecki, Filip, cs.FL, 2018, In 2021, this problem was shown to be non-primitive recursive, independently by Jerome LerouxARXIV, 2104.12695, Leroux, Jérôme, The Reachability Problem for Petri Nets is Not Primitive Recursive, cs.LO, 2021, and by Wojciech CzerwiÅski and Åukasz Orlikowski.ARXIV, 2104.13866, CzerwiÅski, Wojciech, Reachability in vector addition systems is Ackermann-complete, Orlikowski, Åukasz, cs.FL, 2021, 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.Livenessmissing image!
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 all of its transitions are L_k-live, where a transition is - liveness-levels.gif - A Petri net in which transition t_0 is dead, while for all j>0, t_j is L_j-live
Boundedness(File:Reachability graph for petri net.png|right|frame|The reachability graph of N2.)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â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.WEB,www.techfak.uni-bielefeld.de/~mchen/BioPNML/Intro/pnfaq.html , 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.(File:Two-boundedness-ub.png|right|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|right|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., Petri Nets , www.techfak.uni-bielefeld.de Discrete, continuous, and hybrid Petri netsAs 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,BOOK,books.google.com/books?id=VsS0JkMcXGwC, Discrete, continuous, and hybrid Petri Nets, René, David, Hassane, Alla, Springer, 2005, 978-3-540-22480-8, and related to discrete, continuous and hybrid automata.ExtensionsThere 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.BOOK, Jensen, Kurt, Kurt Jensen (computer scientist), A brief introduction to colored Petri nets, 1217, 203â208,link.springer.com/content/pdf/10.1007/BFb0035389.pdf, 10.1007/BFb0035389, A brief introduction to coloured Petri Nets, Lecture Notes in Computer Science, 1997, 978-3-540-62790-6, 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.A short list of possible extensions follows:
Restrictionsthumb|Petri net types graphicallyInstead 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:
Workflow netsWorkflow nets (WF-nets) are a subclass of Petri nets intending to model the workflow of process activities.JOURNAL, van der Aalst, W. M. P., 1998,wwwis.win.tue.nl/~wvdaalst/publications/p53.pdf, The application of Petri nets to workflow management, Journal of Circuits, Systems and Computers, 8, 1, 21â66, 10.1142/s0218126698000043, 10.1.1.30.3125, 248401501, 2015-04-02, 2016-11-19,wwwis.win.tue.nl/~wvdaalst/publications/p53.pdf," title="web.archive.org/web/20161119142948wwwis.win.tue.nl/~wvdaalst/publications/p53.pdf,">web.archive.org/web/20161119142948wwwis.win.tue.nl/~wvdaalst/publications/p53.pdf, dead, 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.BOOK, van Hee, K., Sidorova, N., Voorhoeve, M., 2003,www.win.tue.nl/~sidorova/03/van_Hee_Sidorova_Voorhoeve.pdf, Soundness and separability of workflow nets in the stepwise refinement approach, van der Aalst, W. M. P., Best, E., Application and Theory of Petri Nets 2003, Lecture Notes in Computer Science, 2678, 337â356, Springer, 10.1007/3-540-44919-1_22, 3-540-44919-1, A directed path 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).CONFERENCE, Ping, L., Hao, H., Jian, L., 2004, On 1-soundness and soundness of workflow nets, Daniel, Moldt, Proc of the 3rd Workshop on Modelling of Objects, Components, and Agents, Aarhus, Denmark, DAIMI PB, 571, 21â36, 0105-8517, 872760679, 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).Other models of concurrencyOther ways of modelling concurrent computation have been proposed, including vector addition systems, communicating finite-state machines, Kahn process networks, process algebra, the actor model, and trace theory.BOOK, Antoni, Mazurkiewicz, Introduction to Trace Theory, The Book of Traces, V., Diekert, G., Rozenberg, World Scientific, 1995, 3â67, Different models provide tradeoffs of concepts such as compositionality, modularity, and locality.An approach to relating some of these models of concurrency is proposed in the chapter by Winskel and Nielsen.BOOK, G., Winskel, M., Nielsen,www.cl.cam.ac.uk/~gw104/winskel-nielsen-models-for-concurrency.pdf, Models for Concurrency, Handbook of Logic and the Foundations of Computer Science, 4, 1â148, OUP,web.archive.org/web/20200504155703/https://www.cl.cam.ac.uk/~gw104/winskel-nielsen-models-for-concurrency.pdf, 4 May 2020,Application areas
, J. L.
, Fernandez, Sanz, R., Paz, E., Alonso, C. , Using hierarchical binary Petri nets to build robust mobile robot applications: RoboGraph , IEEE International Conference on Robotics and Automation, 2008. , 1372â7 , 19â23 May 2008 , Pasadena, CA, USA , 10.1109/ROBOT.2008.4543394 | LAST2=LEITãO | LAST3=COLOMBO | LAST4=RESTIVO | TITLE=HIGH-LEVEL PETRI NETS FOR THE PROCESS DESCRIPTION AND CONTROL IN SERVICE-ORIENTED MANUFACTURING SYSTEMS | YEAR=2012 | ISSUE=6 | URL=HTTPS://DOI.ORG/10.1080/00207543.2011.575892 | DOI=10.1080/00207543.2011.575892 | FIRST2 = C. | TITLE = ACTIVE FLOW AND COMBUSTION CONTROL 2018 | CHAPTER = ANALYZING AND COMPLETING MIDDLEWARE DESIGNS FOR ENTERPRISE INTEGRATION USING COLOURED PETRI NETS | SERIES = LECTURE NOTES IN COMPUTER SCIENCE | PAGES = 400â416 | ISBN = 978-3-319-98176-5, free,
See also
References{{reflist|30em}}Further reading{{commons category|Petri nets}}
, Cardoso
, Janette , Heloisa , Camargo , 1999 , Fuzziness in Petri Nets , Physica-Verlag , 978-3-7908-1158-2,
, Chiachio
, Manuel , Chiachio , Juan , Presscott , Darren , Andrews , John , 2018 , A new paradigm for uncertain knowledge representation by ‘Plausible Petri nets’ , Information Sciences , 453 , July 2018 , 323â345 , 10.1016/j.ins.2018.04.029 , free,
, Grobelna
, Iwona , Formal verification of embedded logic controller specification with computer deduction in temporal logic , PrzeglÄ d Elektrotechniczny , 2011 , 87 , 12a , 47â50,
, Jensen
, Kurt , 1997 , Coloured Petri Nets ,archive.org/details/springer_10.1007-978-3-642-60794-3 , Springer Verlag , 978-3-540-62867-5,
, Pataricza
, András , 2004 , Formális módszerek az informatikában (Formal methods in informatics) , TYPOTEX Kiadó , 978-963-9548-08-4,
, Peterson
, James Lyle , Petri Nets , ACM Computing Surveys , 1977 , 9 , 3 , 223â252 , 10.1145/356698.356702 , 10338.dmlcz/135597 , 3605804 , free,
, Peterson
, James Lyle , 1981 , Petri Net Theory and the Modeling of Systems , Prentice Hall , 978-0-13-661983-3,
, Petri
, Carl Adam , Kommunikation mit Automaten , University of Bonn , 1962 , Ph. D.,
, Petri
, Carl Adam , Reisig , Wolfgang , Petri net , Scholarpedia , 3 , 4 , 6477 , 10.4249/scholarpedia.6477 , 2008 , 2008SchpJ...3.6477P , free,
, Reisig
, Wolfgang , 1992 , A Primer in Petri Net Design , Springer-Verlag , 978-3-540-52044-3,
, Riemann
, Robert-Christoph , 1999 , Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus , Herbert Utz Verlag , 978-3-89675-629-9,
, Störrle
, Harald , 2000 , Models of Software Architecture â Design and Analysis with UML and Petri-Nets , Books on Demand , 978-3-8311-1330-9,
, Zaitsev
, Dmitry , 2013 , Clans of Petri Nets: Verification of protocols and performance evaluation of networks , LAP LAMBERT Academic Publishing , 978-3-659-42228-7 ,www.morebooks.de/store/gb/book/clans-of-petri-nets/isbn/978-3-659-42228-7,
, Zhou
, Mengchu , Mengchu Zhou , Dicesare , Frank , 1993 , Petri Net Synthesis for Discrete Event Control of Manufacturing Systems , Kluwer Academic Publishers , 978-0-7923-9289-7,
, Zhou
, Mengchu , Mengchu Zhou , Venkatesh , Kurapati , 1998 , Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach , World Scientific Publishing , 978-981-02-3029-6,
, Xue-Guo
{{Authority control}}, Xu , Picture Fuzzy Petri Nets for Knowledge Representation and Acquisition in Considering Conflicting Opinions , Applied Sciences , 2019 , 9 , 5 , 983 , 10.3390/app9050983 , free, |
- content above as imported from Wikipedia
- "Petri net" does not exist on GetWiki (yet)
- time: 6:30am EDT - Wed, May 22 2024
- "Petri net" does not exist on GetWiki (yet)
- time: 6:30am EDT - Wed, May 22 2024
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 21 MAY 2024
The Illusion of Choice
Culture
Culture
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
© 2024 M.R.M. PARROTT | ALL RIGHTS RESERVED