Математическая энциклопедия - петри сеть

математическая модель дискретных динамич. систем, в том числе информационных систем (параллельных программ, операционных систем, ЭВМ и их устройств, сетей ЭВМ), ориентированная на качественный анализ и синтез таких систем (обнаружение блокировок, тупиковых ситуаций и узких мест, автоматич. синтез параллельных программ и компонентов ЭВМ и др.). Введена К. Петри (С. Petri) в 60-х гг. 20 в. П. с.это набор N=( Т, Р, F, М 0), где Т - конечное множество символов, наз. переходами, Р - конечное множество символов, наз. местами, функция инцидентности:

M0 начальная разметка мест:

Неформально П. с. представляют размеченным ориентированным графом со множеством вершин (см. рис.). Из вершины-места , изображаемой кружком, ведет дуга в вершину-переход , изображаемую прямоугольником, тогда и только тогда, когда

( р- входное место перехода t;. на рис. P={p1, р 2, p3], Т={а, b, с, d}). Из вершины-перехода tведет дуга в вершину-место ртогда и только тогда, когда F(t,p) = 1 (р выходное место перехода t). Место рпомечается разметкой , часто изображаемой соответствующим числом точек (фишек).

Динамика поведения моделируемой системы описывается в терминах функционирования П. с. Сеть функционирует в дискретном времени, переходя от разметки к разметке. Каждая разметка это функция {0,1,2,...}; смена разметок (начиная с M0) происходит в результате срабатывания переходов сети.

Переход может сработать при разметке М, если для любого

т. е. если каждое его входное место имеет хотя бы одну фишку. В результате срабатывания tпри разметке Мпоследняя сменяется разметкой М' по правилу: для любого

т. е. переход tизымает по фишке из каждого своего входного места и посылает по фишке в каждое свое выходное место. Если может сработать несколько переходов, то срабатывает один, любой из них. Сеть останавливается, если при нек-рой разметке (тупиковая разметка) ни один из ее переходов не может сработать. При одной и той же начальной разметке П. с. может порождать, в силу недетерминированности ее функционирования, различные последовательности срабатываний ее переходов. Эти последовательности образуют слова в алфавите Т, а множество всевозможных слов, порождаемых П. с., наз. ее языком. Две П. с. эквивалентны, если они порождают один и тот же язык.

Исследования по П. с. развиваются в двух направлениях. Математич. теория сетей разрабатывает методы формального анализа их свойств. Среди наиболее интересных проблем следует отметить задачи распознавания тупиковых ситуаций в сетях, задачи распознавания эквивалентности сетей по порождаемым языкам, оценки сложности анализа сетей, сравнение выразительной мощности различных подклассов П. с. и их обобщений. Установлено, что проблема тупиковых ситуаций разрешима, изучены свойства класса языков, порождаемых П. с. Этот класс строго содержится в классе рекурсивно перечислимых языков, строго включает класс регулярных языков и частично пересекается с классом контекстно свободных языков. Второе направление применение П. с. как основы прикладных моделей дискретных динамич. систем в информатике, экономике, цифровой технике и т. п.

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

Лит.:[1] Peterson J. L., Petri net theory and the modeling of systems, Englewood-Cliffs, 1981; [2] Котов В. Е., "Кибернетика", 1980, № 5, с. 10-18; [3] Апериодические автоматы, М., 1976; [4] Net theory arid applications, В., 1980.

В. Е. Котов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985