Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 35
Текст из файла (страница 35)
Если 1, не может быть запущен из-за того, что р; пуста, то тогда и только тогда будет запущен переход 1,. Хэк показал способ преобразования сетей Петри с приоритетами в сети Петри со сдерживающими дугами, и наоборот 11151. Временные сети Петри также могут осуществлять проверку позиции на нуль, моделируя приоритеты. Если мы имеем два перехода 11 и 1„ И УСтаыаВЛИВаЕМ тт,; с т1 Ы тО ПЕРЕХОД 11 ИМЕЕТ ПРИОРИтЕт НЗД ПЕ- реходом 1к, поскольку 11 должен запускаться (если он разрешен) до того, как 1„ мог бы быть разрешен для запуска. 1.3. Расширенные сети Петри н регистровые мешины Мы показали, что все предложенные расширения модели сетей Петри допускают возможность проверки позиции на нуль.
Насколько это важно по отношению к мощности разрешения сетей Петри? Влияет ли это на возможность анализа сетей Петри? Проверка на нуль уменьшает мощность разрешения сети Петри. Агервала 141, Хэк 1115], Томас Ю01 и др. показали, что появление способности проверки на нуль у модели сетей Петри позволяет се- Расширенные и ограни«енные модели сетей Петри тям Петри моделировать машину Тьюринга.
Таким образом, сети Петри с проверкой на нуль дают схему моделирования, с помощью которой можно моделировать любую систему. Однако почти все вопросы анализа сетей Петри становятся неразрешимыми, поскольку они неразрешимы для машин Тьюринга. Доказательство эквивалентности расширенных сетей Петри и машин Тьюринга относительно просто. Легче всего его представить в терминах регистровых машин Шепардсона н Стургиса (276) или программных машин Минского (200!. Регистровая машина есть абстрактная модель ЭВМ с несколькими регистрами, которые используются для хранения произвольно болыпих чисел.
Для манипулирования этими регистрами пишется программа. Программа есть последовательность инструкций вида «увеличить регистр и на 1», «уменьшить регистр и на 1 (только если регистр и не равен О)», «перейти к предложению з, если регистр и не равен нулю», и т. д. Ниже представлена программа сложения содержимого регистра 2 с регистром 1. 1. Если регистр 2 равен нулю, то идти к инструкции 5. 2. Вычесть 1 нз регистра 2.
, 3. Прибавить 1 к регистру 1. 4. Идти к инструкции 1. 5. Стоп. Шепардсон и Стургис показали, что регистровая манан|а со следующими инструкциями эквивалентна машине Тьюринга. 1. Р(и): увеличить регистр и на 1. 2. В(и): уменьшить регистр и на 1 (регистр и не равен нулю). 3. е'(и) Ь1: перейти к предложению з, если регистр и равен нулю.
Таким образом, если регистровая машина может быть преобразована в эквивалентную сеть Петри, то тем самым будет показано, что расширенные сечи Петри эквивалентны регистровым машинам. Это преобразование относительно просто. Для представления регистровой машины расширенной сетью Петри представим и регистров, используемых в программе, и позициями рь р«, ", р . Мы также используем з + 1 позицию для представления положения счетчика инструкций либо пер~д предложением 1 (начальная маркировка), либо после предложения г для 1 = 1, ..., з в программе из з предложений.
Каждая инструк , ция в программе представляется переходом. На рис. 7.12 показано как каждая из трех вышеприведенных инструкций представляется переходом в расширенной сети Петри. Из этого видно, что рег"ст ровая машина может быть преобразована в расширенную сеть Петри, и, следовательно, расширенная сеть Петри эквивалентна ма шине Тьюринга. Эта эквивалентность машине Тьюринга разрушает все надежды на возможность анализа расширенных сетей Петри. Однако это же доказывает, что расширенные сети Петри могут мод~ лировать любую систему (или по крайней мере любую вьпгясл" мую систему).
Таким образом, мы видим, что увеличение могцности Глава 7 Р« Ркс. 7.12. Преобразонанпе кнструкцви (номер л) регистровой машаны в переход расширенной сети Петри со сдержнвающпин дугами. а — Р(л)л увеличать содержимое регистра и на 1; б — ь1(и)г уменьшить солнржнмое регистра и на 1 (содержимое регистра и должво быть положительным), в — .Цл)(а): переход к инструкции а в случае нулевого значения регистра л.
моделирования в этом случае приводит к определенному уменьшению мощности разрешения. Отметим также, что ключевым моментом в доказательстве эквивалентности сетей Петри, регистровых машин и машин Тьюринга является способность к проверке одной позиции на нуль. Таким образом, все предложенные расширения — области ограничения, переходы исключающее ИЛИ, переключатели, приоритеты, интервалы времени и сдержнваюшне дуги — расширяют модели сетей Петри до уровня мшпин Тьюринга. Существуют другие предложения по расширению, которые не поднимают сети Петри до уровня машин Тьюринга. Первыми в качестве расширений были предложены петли и кратные входные и выходные дуги. Но как зто было показано н разд. 5.3, такие сети Петри фактически эквивалентны простым сетям Петри.
Аналогично добавление входов ИЛИ, выходов ИЛИ, выходов исключающее ИЛИ не увеличило бы мощность моделирования сетями Петри. Ригтииренные и ограниченные модели сетей Петри Вообще, кажется, что любое расширение, которое ие позволяет проверку на нуль, в действительности не увеличивает мощность моделирования (нли не уменьшает мощность разрешения) сетей Петри, но приводит просто к другой эквивалентной формулировке модели сети Петри (может возрасти удобство моделирования). В то же самое время любое расширение, которое разрешает проверку на нуль, увеличивает мощность моделирования до уровня машин Тьюринга и сводит мощность разрешения к нулю. 1.4.
Подклассы сетей Петри Цель расширения сетей Петри состоит в увеличении их мощности моделирования. К несчастью, побочным эффектом такого расширения является значительное уменьшение мощности разрешения расширенных сетей Петри. Мощность разрешения обычных сетей Петри также сомнительна из-за их сложности и обширности (вспомните результаты разд.
5.8 по сложности задач достижнмости и ограниченности). Это привело к появлению некоторых исследований подклассов сетей Петри. Цель этих исследований состоит в определении разумных структурных ограничений, налагаемых на сети Петри, которые увеличивают мощность разрешения ограниченных моделей сетей Петри, не ограничивая существенно мощность моделирования. Многие задачи, связанные с подклассами сетей Петри, могут быть решены. И цель этой части исследований сетей Петри достаточно проста: определить подкласс сетей Петри, который может моделировать большой класс систем (все или почти все интересующие нас системы), но для которого еще существуют простые процедуры анализа (по крайней мере для интересующих нас проблем).
Необходимо также, чтобы существовал простой способ для определения, является ли какая-либо сеть Петри членом определенного подкласса. Все определенные подклассы являются синтаксическими или структурными подклассами, и можно легко проанализировать структуру сети Петри для выяснения, является ли эта сеть Петри членом определенного подкласса. В этом их отличие от подклассов, которые можно определить в соответствии с динамическими свойствами, такими, как устойчивые сети Петри (! 61) или ограниченные сети Петри.
Такие подклассы могут иметь очень хорошие свойства, но для них очень трудно определить, является ли произвольная данная сеть Петри устойчивой или ограниченной. Достаточно полно изучены только два главных подкласса модели сетей Петри: автоматные сети Петри н маркированные ерагры. Кроме того, Хэк!107) изучил подкласс, названный сетями Петри со свободным выбором, и сформулировал предположения, что другой подкласс, правильные сети Петри могут иметь хорошие свойства с точки зрения разрешимости.
Мы представим каждый из этих классов и укажем их основные свойства, достоинства и недостатки. Глава 7 7.4Л. Автоматные сети Петри Автоматная сеть Петри — это сеть Петри, в которой каждый переход может иметь точно один выход и один вход. Определение 7.1.
Автоматлная сеть Петри — это сеть Петри С= (Р, Т, 7, О) — такая, что для всех 1; Е Т, ~7(1;) ~ = 1 и !0(1;) ~ = = 1. Некоторые свойства автоматных сетей Петри очевидны. Прежде всего автоматные сети Петри — строго сохранякхцие. Это означает, что число фишек в такой сети никогда не изменяется, и мы получаем таким образом конечную систему. Отсюда следует, что дерево достижимости для автоматной сети Петри является конечным, и, следовательно, все вопросы анализа для автоматных сетей Петри разрешимы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
