683
правки
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. | ||
[[Категория:Теория вычислений]] |