65. Живые сети Петри – проблема селекции потенциальных тупиков.

Определение:Если переход в любой маркировке из множества достижимости потенциально разрешим, то онживой.

Определение:Если все переходы в сети активны, тосеть называется живой.

Определение:Потенциально разрешимый переход:

Ø – тупиковая, т.к. селектор пустой.

Маркировка , при которой ни одно событие сетиN невозможно –тупиковая маркировка.

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

Селекция тупиков– нахождение тупиковых состояний. Эта проблема сводится к проблеме определения живости сети.

Про ловушки ваще-то вроде ничего знать мы не обязаны, но на всяк случай оставляю эту лабуду…

Ловушка– это такое множество позиций, что каждый переход, входом для которого является одна из позиций множества, имеет выходом другую позицию тоже множества. Это означает, что если в какой-либо позиции ловушки имеется фишка, то она будет в одной из позиции ловушки всегда.

Хэк доказал, что необходимым и достаточным условием активностимаркированной сети Петри со свободным выбором является требование того, чтобы каждый тупик содержал ловушку с фишкой.

(Что такое сети своб. выбора – см. вопрос 67.)