Petri net: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Petri net''' --- сеть Петри. A ''' Petri net''' is a finite directed graph with two types of nodes, referred to as '''places''' and '''transitions'''.…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Petri net''' --- сеть Петри. | '''Petri net''' ---''[[сеть Петри]]''. | ||
A ''' Petri net''' is a finite directed graph with two types of nodes, | A ''' Petri net''' is a finite directed graph with two types of nodes, | ||
referred to as '''places''' and '''transitions'''. It is a bipartite graph: every arc | referred to as '''places''' and '''transitions'''. It is a bipartite graph: every arc | ||
goes either from a place to a transition or from a transition to a place. | goes either from a place to a transition or from a transition to a place. | ||
Consider a transition <math>t</math>. Every place <math>p</math> (respectively, <math>q</math>) such that there is an arc from <math>t</math> to <math>p</math> | Consider a transition <math>t</math>. Every place <math>p</math> (respectively, <math>q</math>) such that there is an arc from <math>t</math> to <math>p</math> | ||
(respectively, from <math>q</math> to <math>t</math>) is called an '''input''' | (respectively, from <math>q</math> to <math>t</math>) is called an '''input''' | ||
( | (respectively, an '''output''') '''place''' of <math>t</math>. | ||
The same place can be both an input and an output place of <math>t</math>. | The same place can be both an input and an output place of <math>t</math>. | ||
| Строка 16: | Строка 15: | ||
Thus, formally, a (marked) Petri net is a quadruple <math>N=(P,T,A,m_0)</math>, where <math>P</math> and <math>T</math> are nonempty | Thus, formally, a (marked) Petri net is a quadruple <math>N=(P,T,A,m_0)</math>, where <math>P</math> and <math>T</math> are nonempty | ||
finite disjoint sets of places and | finite disjoint sets of places and transitions, <math>A</math> is a subset of <math>P \times T \bigcup T\times P</math>. | ||
(It is often also required that the union of the domain and codomain of <math>A</math> equals <math>P\bigcup T</math>; that is, | (It is often also required that the union of the domain and codomain of <math>A</math> equals <math>P\bigcup T</math>; that is, | ||
every place and transition is either the beginning or the end of some arc.) Finally, <math>m_0</math> (initial marking) | every place and transition is either the beginning or the end of some arc.) Finally, <math>m_0</math> (initial marking) | ||
| Строка 23: | Строка 22: | ||
We now define the '''operation''' (or '''execution''') of a Petri net. | We now define the '''operation''' (or '''execution''') of a Petri net. | ||
A transition is '''enabled''' (at a marking) iff all its input places have at least one token. | A transition is '''enabled''' (at a marking) iff all its input places have at least one token. | ||
An enabled | An enabled transition may '''fire''' by removing one token from each of its input places and | ||
adding one token to each of its output places. | adding one token to each of its output places. | ||
| Строка 39: | Строка 38: | ||
A transition is not enabled if there are not sufficiently many tokens in each | A transition is not enabled if there are not sufficiently many tokens in each | ||
of its input places. | of its input places. | ||
[[Категория:Теория вычислений]] | |||
Текущая версия от 16:04, 17 сентября 2018
Petri net ---сеть Петри.
A Petri net is a finite directed graph with two types of nodes, referred to as places and transitions. It is a bipartite graph: every arc goes either from a place to a transition or from a transition to a place. Consider a transition [math]\displaystyle{ t }[/math]. Every place [math]\displaystyle{ p }[/math] (respectively, [math]\displaystyle{ q }[/math]) such that there is an arc from [math]\displaystyle{ t }[/math] to [math]\displaystyle{ p }[/math] (respectively, from [math]\displaystyle{ q }[/math] to [math]\displaystyle{ t }[/math]) is called an input (respectively, an output) place of [math]\displaystyle{ t }[/math]. The same place can be both an input and an output place of [math]\displaystyle{ t }[/math].
A marking of a Petri net is a mapping [math]\displaystyle{ m }[/math] of the set of places into the set of nonnegative integers. The fact that [math]\displaystyle{ m(p)=k }[/math] is usually visualized by saying that there are [math]\displaystyle{ k }[/math] tokens in the place [math]\displaystyle{ p }[/math]. A specific initial marking [math]\displaystyle{ m_0 }[/math] is usually given in the definition of a Petri net.
Thus, formally, a (marked) Petri net is a quadruple [math]\displaystyle{ N=(P,T,A,m_0) }[/math], where [math]\displaystyle{ P }[/math] and [math]\displaystyle{ T }[/math] are nonempty finite disjoint sets of places and transitions, [math]\displaystyle{ A }[/math] is a subset of [math]\displaystyle{ P \times T \bigcup T\times P }[/math]. (It is often also required that the union of the domain and codomain of [math]\displaystyle{ A }[/math] equals [math]\displaystyle{ P\bigcup T }[/math]; that is, every place and transition is either the beginning or the end of some arc.) Finally, [math]\displaystyle{ m_0 }[/math] (initial marking) is a mapping of [math]\displaystyle{ P }[/math] into the set of nonnegative integers.
We now define the operation (or execution) of a Petri net. A transition is enabled (at a marking) iff all its input places have at least one token. An enabled transition may fire by removing one token from each of its input places and adding one token to each of its output places.
The operation of a Petri net starts with the initial marking [math]\displaystyle{ m_0 }[/math]. Whenever some transition is enabled, it may fire. This leads to a new marking. If more than one transition is enabled, the firing of such transitions is viewed in an asynchronous fashion: They may fire simultaneously or at different times, one after another. If two transitions have common input places, they are said to be in conflict. This means that only one of them can fire at any marking.
A Petri net defined above is an ordinary Petri net. A general definition of a Petri net is obtained by introducing multiplicities for arcs. Multiplicities means that there is an integer greater than or equal to 1 associated to each arc. The multiplicity of an arc indicates the number of tokens to be subtracted from the input place, as well as the number of tokens to be added to the output place. A transition is not enabled if there are not sufficiently many tokens in each of its input places.
