Теория сетей Петри

Материал из DvoWiki
Перейти к: навигация, поиск

Теория сетей Петри является хорошо известным и популярным формализмом, предназначенным для работы с параллельными и асинхронными системами. Основанная в начале 60-х годов немецким математиком К.А.Петри [??], в настоящее время она содержит большое количество моделей, методов и средств анализа, имеющих обширное количество приложений практически во всех отраслях вычислительной техники и даже вне ее.

Мультимножества

Пусть A=\{a_{1},a_{2},...,a_{k}\} есть некоторое множество. Мультимножеством на множестве A есть функция \mu :A\rightarrow {0,1,2,...}, которая каждому элементу множества A ставит в соответствие неотрицательное целое число. Мультимножества удобно записывать в виде формальной сумму n_{1}a_{1}+n_{2}a_{2}+...+n_{k}a_{k} или \Sigma n_{i}a_{i}, где n_{i}=\mu (a_{i}) есть число вхождений a_{i}\in A в мультимножество. Как правило, при записи суммы её элементы с n_{i}=0 опускаются. Объединение и пересечение двух мультимножеств \mu _{1}=n_{1}a_{1}+n_{2}a_{2}+...+n_{k}a_{k} и \mu _{2}=m_{1}a_{1}+m_{2}a_{2}+...+m_{k}a_{k} на множестве A, определяется соответственно как \mu _{1}+\mu _{2}=(n_{1}+m_{1})a_{1}+(n_{2}+m_{2})a_{2}+...+(n_{k}+m_{k})a_{k} и \mu _{1}-\mu _{2}=(n_{1}-m_{1})a_{1}+(n_{2}-m_{2})a_{2}+...+(n_{k}-m_{k})a_{k}, где последняя операция производится только тогда, когда n_{i}>m_{i} ддя всех 1\leq i\geq k. Мы будем писать \mu _{1}\leq \mu _{2}, если n_{i}\leq m_{i} ддя каждого 1\leq i\geq k, и \mu _{1}<\mu _{2}, если \mu _{1}\leq \mu _{2} и \mu _{1}\neq \mu _{2}. Если n_{i}=0 для всех i, тогда такое мультимножество будет обозначаться как {\textbf  {0}}. Мы будем также писать, что a\in \mu , если \exists n>0:(a,n)\in \mu .

Множество всех конечных мультимножеств на множестве A будет обозначаться как {\mathcal  {M}}(A). Множество всех конечных последовательностей, составленное из символов множества A, включая пустую строку \epsilon , будет обозначаться как A^{*}.

Простые сети Петри

Сеть Петри определяется как набор \Sigma =\langle S,T,^{\bullet }(),()^{\bullet },M_{0}\rangle , где

  1. S есть конечное множество мест
  2. T есть конечное множество переходов такое, что S\cap T=\emptyset
  3. ^{\bullet }():T\rightarrow {\mathcal  {M}}(S) есть входная функция инцидентности
  4. ()^{\bullet }:T\rightarrow {\mathcal  {M}}(S) есть выходная функция инцидентности
  5. M_{0}\in {\mathcal  {M}}(S) есть начальная маркировка.

Мультимножества ^{\bullet }t и t^{\bullet } называются входными и выходными множествами перехода t\in T соответственно. Функции ^{\bullet }() и ()^{\bullet } могут быть естественно расширены на мультимножества ^{\bullet }(n_{1}t_{1}+n_{2}t_{2}+...+n_{k}t_{k})=n_{1}^{\bullet }t_{1}+n_{2}^{\bullet }t_{2}+...+n_{k}^{\bullet }t_{k} и (n_{1}t_{1}+n_{2}t_{2}+...+n_{k}t_{k})^{\bullet }=n_{1}t_{1}^{\bullet }+n_{2}t_{2}^{\bullet }+...+n_{k}t_{k}^{\bullet }.