![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
П р о ц е д у р а
1. М0 = (M0(p1), M0(p2),., M0(p½ P½ )) - начальная разметка сети Петри. Она обозначает корневую вершину дерева достижимости. 2. M = (M(p1), M(p2),., M(p½ P½ )) - разметка сети Петри, обозначающая граничную вершину дерева достижимости, еще не обработанную данной процедурой. Применяя процедуру к граничной вершине, можно получить варианты: 2.1. M - концевая терминальная вершина дерева, если при M нет возбужденных переходов; 2.2. M - концевая дублирующая вершина дерева, если в уже построенной части дерева существует вершина, имеющая разметку, совпадающую с M;
M+ = (M+(p1), M+(p2),., M+ (p½ P½ )),. M M+, непосредственно достижимую из M. При этом маркировки позиций в разметке M+ определяются по следующим правилам: 2.3.1. Если M(pi) = w, то M+(pi) = w, pi Î P; Символ w означает возможность получения как угодно большого числа маркировок M+(pi) вследствие циклического запуска перехода tj; 2.3.2. Если на пути от M0 к M в уже построенной части дерева найдется вершина, представляющая разметку M- = (M-(p1), M-(p2),., M-(p½ P½ )) такую, что M- < M+ и M-(pi) < M+(pi), то M+(pi) = w, pi Î P; 2.3.3. В случаях, отличных от рассмотренных в пп. 2.3.1 и 2.3.2, маркировки позиций новой разметки сети M+ находятся обычным образом:
M+(pi) = M(pi) - W(pi, tj), pi Î I(tj); tj Î T.
Ограниченность. При моделировании систем, функционирование которых связано с процессами перемещения (передачи) и накопления материальных ингредиентов (единиц информации), действуют ограничения на вместимость накопителей или общее допустимое количество единиц материального (информационного) потока в системе. Позиция pi Î P сети Петри C=(P, T, E, W, M0) является S-ограниченной, если существует число S Î N такое, что " Mk Î M(C, M0): Mk(pi) £ S. Сеть Петри называется S-ограниченной, если любая её позиция S - ограниченная. Особый случай - ограниченность сетей при S = 1. Такие сети называются безопасными. Любая достижимая на безопасной сети разметка задается вектором из нулей и единиц. Консервативность. Свойство ограниченности тесно связано со свойством сохранения (консервативности) сетей Петри. В сохраняющих сетях общая сумма меток всех позиций остается постоянной величиной на любом шаге выполнения сети. Это означает, что при срабатывании любого перехода общая сумма меток не изменяется и остается равной сумме меток позиций сети в её начальном состоянии. В общем виде свойство сохранения определяется равенством вида: " Mk, Mr Î M(C, M0): å i ai Mk(pi) = å i ai Mr(pi), ai Î N, pi Î P, (a1, a2,., a|P|) - вектор весов. При (a1, a2,., a|P|) = (1, 1,., 1) в сети выполняется " строгое сохранение": " Mk, Mr Î M(C, M0): å i Mk(pi) = å i Mr(pi)), откуда следует: " tj Î T: |O(tj)| = |I(tj)|. Проблема ограниченности сетей Петри разрешима. Полезным инструментом анализа ограниченности является дерево достижимости сети. С его помощью можно проверить безопасность и S- ограниченность отдельных позиций и сети в целом, а также установить, какие именно позиции данной сети являются в ней неограниченными (позиции с маркировкой w). Проблема сохранения в сетях Петри также разрешима. Для сохраняющей сети выполняются равенства å i ai Mk(pi) = å i ai M0(pi), Mk Î M(C, M0). Переходя к матричным представлениям, получим Mk aT = M0 aT. Поскольку Mk = M0 + m(s)R, где R - матрица сети, то RaT = 0. Тем самым сеть Петри будет сохраняющей тогда и только тогда, когда существует вектор весов a = (a1, a2,., a|P|) с положительными компонентами (ai > 0), удовлетворяющий уравнению RaT = 0. Активность, живость, тупики. Всякий переход tj Î T сети Петри будет активным, если в этой сети существует разметка Mk Î M(C, M0), при которой данный переход может сработать. Переходы различаются по уровням активности. Тупиковые (пассивные) переходы имеют активность нулевого уровня. Переход, получающий в сети возбуждение, обладает активностью первого уровня. Переход tj Î T называют живым, если для любой исходной разметки M0 в сети достигается разметка Mk Î M(C, M0), при которой этот переход получает возбуждение. Сеть C = (P, T, E, W, M0) - живая, если все её переходы живые. Переход tj Î T характеризуется активностью второго уровня, если для произвольно взятого числа n Î N в сети Петри с начальной разметкой M0 существует последовательность срабатываний s, в которой переход tj будет запускаться не менее n раз. Переход tj Î T относится к переходам третьего уровня активности, если в сети Петри возможна бесконечная последовательность срабатываний, в которой tj будет запускаться неограниченное число раз. Переход tj Î T имеет четвертый уровень активности, если при любой разметке Ms, достижимой от Mk, в сети Петри возможна последовательность срабатываний переходов, в результате выполнения которой установится разметка Mr, обеспечивающая запуск перехода tj.
|