Сеть Петри

Сеть Петри (Petri net) — Графическая модель системы с высокой степенью распараллеливания вычислений, используемая для анализа определенных ее свойств. Сеть Петри состоит из множества узлов (мест), множества символов, переходов и множества дуг. Каждый переход связывается с соответствующим множеством входных мест и соответствующим множеством выходных мест. Каждый переход соединяется с каждым из входных мест дугой, идущей из узла-места к переходу, и с каждым выходным местом — дугой, направленной от перехода к узлу-месту.

Состояние параллельной системы представляется наличием определенных меток у узлов, а конкретное состояние отображается конкретной конфигурацией меток. Такое распределение меток между местами называется разметкой. Узлы обычно изображаются в виде кружков, обозначаемых строчными буквами [math]\displaystyle{ p \ldots t }[/math], переходы — линиями, а текущая разметка — черными точками (фишками). Символы переходов показывают возможные изменения состояния параллельной системы.

Переход может срабатывать (отображая смену состояния) только тогда, когда каждое из его входных мест имеет по меньшей мере одну метку (фишку). Когда переход срабатывает, происходит изъятие метки из каждого его входного места и пересылка по одной метке в каждое из его выходных мест. Таким образом, комбинация входных и выходных мест некоторого перехода отображает как условия, при которых может произойти изменение состояния, так и влияние этого изменения.

Срабатывание перехода — это неделимое событие, и потому одновременное срабатывание двух или более переходов невозможно. Когда состояние таково, что два или более переходов претендуют на срабатывание, каждый из них должен рассматриваться отдельно.

Начиная с начальной разметки, которая соответствует исходному (начальному) состоянию системы, и выполняя очевидную процедуру генерирования другой разметки, достижимой из текущей за счет срабатывания некоторого перехода, можно исследовать возможные состояния системы и пути их достижения. Например, могут быть легко обнаружены тупиковые состояния и непродуктивные зацикливания и вообще всегда можно установить, соответствует ли поведение системы ожидаемому. Хотя процедура генерации достижимой разметки довольно тривиальна, попытки исчерпывающего анализа поведения системы таким способом оказываются тщетными часто из-за уже одного только числа разметок, которое может быть бесконечным. Таким образом, главная задача, состоящая в определении достижимости данной разметки из заданного исходного состояния, пока не поддается решению. Неоднократные попытки доказать общепринятую гипотезу о разрешимости последней, страдали одним общим недостатком — в доказательствах были обнаружены ошибки. Вместе с тем многие другие проблемы сетей Петри эквивалентны ей в том смысле, что их разрешимость или неразрешимость непосредственно следует из разрешимости или неразрешимости проблемы достижимости.

Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри.

Литература

• Котов В.Е. Сети Петри. — М.: Наука, 1984.

• Толковый словарь по вычислительным системам. — М.: Машиностроение,1991.

• Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: ИНЦ НГУ, 2018.