Skip to main content

Petri net

Petri net A model of a concurrent system that is expressed in a specific graphical notation and can be used to explore certain properties of the system. A Petri net consists of a set of places, a set of transition bars, and a set of directed edges. Each transition bar has an associated set of input places and an associated set of output places. A transition bar is linked to each of its input places by a directed edge from the place to the bar, and to each of its output places by a directed edge from the bar to the place.

States of the concurrent system are represented by the presence of tokens at places, with a specific state being represented by a specific allocation of tokens to places. Such an allocation is called a marking.

The example net shown in the diagram employs the conventional graphical notation. Places are represented by the circles labeled p … t, transition bars are represented by the lines labeled B1 … B4, and the initial marking is shown by the use of dots to represent tokens.

Transition bars represent possible changes of state in the concurrent system. A transition bar can only fire (i.e. the change of state occur) when each of its input places holds at least one token. When a bar fires it removes one token from each of its input places and deposits one token at each of its output places. Thus the combination of the input and output places for a transition bar represents both the conditions under which the change of state can occur and the effects of that state change.

The firing of a transition bar is an indivisible event and simultaneous firing of two or more bars is therefore not possible. When the state is such that two or more bars are candidates to fire, each candidate must be considered individually.

By starting from an initial marking that represents an initial state of the system and applying a straightforward procedure that generates other markings that can be reached from this initial marking, it is possible to explore the possible states of the system and the ways in which these states can be reached. For example, both deadlock states and unproductive looping can be readily detected, and in general it is possible to check that the behavior of the system is as expected. However, while the procedure for generating reachable markings is straightforward, attempts at full analysis are often frustrated by the sheer number of such markings, and this can be infinite. Thus the general problem of determining whether a given marking is reachable from a given initial state is undecidable.

With the initial marking shown in the example net, both B1 and B3 are able to fire. Suppose that B1 fires. This removes the tokens from places p and t, and deposits a single token at place q. Now only B2 is able to fire. (B3 is no longer able to fire because there is no longer a token at place t.) When B2 fires, the token is removed from place q and new tokens are deposited at places p and t, thus restoring the initial marking. Should B3 now fire, a single token is deposited at place s, and B4 then fires, again restoring the initial marking. (This net may be viewed as modeling a system in which two processes compete for a shared resource. Availability of the resource is represented by the presence of a token at place t. Relevant states of one process, holding the resource or not holding the resource, are represented by tokens at places p and q respectively. Similarly tokens at places r and s represent relevant states of the other process.)

Petri nets were devised in the early 1960s by C. A. Petri.

Cite this article
Pick a style below, and copy the text for your bibliography.

  • MLA
  • Chicago
  • APA

"Petri net." A Dictionary of Computing. . Encyclopedia.com. 20 Oct. 2018 <http://www.encyclopedia.com>.

"Petri net." A Dictionary of Computing. . Encyclopedia.com. (October 20, 2018). http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/petri-net

"Petri net." A Dictionary of Computing. . Retrieved October 20, 2018 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/petri-net

Learn more about citation styles

Citation styles

Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).

Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.

Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the most-recent information available at these sites:

Modern Language Association

http://www.mla.org/style

The Chicago Manual of Style

http://www.chicagomanualofstyle.org/tools_citationguide.html

American Psychological Association

http://apastyle.apa.org/

Notes:
  • Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
  • In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.