65. Живые сети Петри – проблема селекции потенциальных тупиков.
Определение:Если переход в любой маркировке из множества достижимости потенциально разрешим, то онживой.
Определение:Если все переходы в сети активны, тосеть называется живой.
Определение:Потенциально разрешимый переход:
Ø – тупиковая, т.к. селектор пустой.
Маркировка , при которой ни одно событие сетиN невозможно –тупиковая маркировка.
Тупикесть такое множество позиций, что каждый переход, который имеет в качестве выхода одну из позиций тупика, использует какую-либо позицию тупика в качестве входа. Это означает, что если все позиции тупика в какой-то момент времени станут пустыми, то все это множество позиций останется пустым всегда. Ни один переход не может поместить фишку в тупик потому, что в тупике нет фишек, которые сделали разрешенным этот переход, выходом которого служит позиция из тупика.
Селекция тупиков– нахождение тупиковых состояний. Эта проблема сводится к проблеме определения живости сети.
Про ловушки ваще-то вроде ничего знать мы не обязаны, но на всяк случай оставляю эту лабуду…
Ловушка– это такое множество позиций, что каждый переход, входом для которого является одна из позиций множества, имеет выходом другую позицию тоже множества. Это означает, что если в какой-либо позиции ловушки имеется фишка, то она будет в одной из позиции ловушки всегда.
Хэк доказал, что необходимым и достаточным условием активностимаркированной сети Петри со свободным выбором является требование того, чтобы каждый тупик содержал ловушку с фишкой.
(Что такое сети своб. выбора – см. вопрос 67.)
- 49. Сетевая модельная интерпретация. Синтаксис и семантика сетевой объектной модели.
- 50. Динамика поведения сетевой объектной модели. Основные соглашения выполнения сети.
- 51. Предметная интерпретация. Применение сетей Петри.
- 52. Сети Петри: определение, структура, способы задания.
- 53. Маркированные сети Петри. Начальная и текущая маркировки. Активные переходы и понятие селектора. Срабатывание перехода.
- 54. Выполнение сети: неделимость перехода к следующему состоянию. Функция следующего состояния. Дуальность представления асинхронных процессов в терминах сети Петри.
- 55. Система переходов Келлера и сетевая объектная модель асинхронных процессов. Отношение содержательного соответствия между основными понятиями.
- 56. Обобщение функции следующего состояния. Понятие достижимости.
- 57. Области задания и значений обобщенной функции следующего состояния. Отношение достижимости маркировок сети. Свойства отношения достижимости.
- Область значений:
- 58. Множество достижимости сети. Пространство и множество допустимых маркировок.
- 59. Граф достижимости сети Петри. Конечные и неограниченные графы достижимости.
- 60. Глобальные свойства сетевой объектной модели.
- 61. Динамические свойства сетей Петри.
- 62. Уровни активности переходов по Питерсону. (Раевский с.)
- 63. Отношение конфликтности переходов и устойчивые сети Петри.
- 64. Задачи анализа сетей Петри.
- 65. Живые сети Петри – проблема селекции потенциальных тупиков.
- 66. Структурные подклассы обычных сетей Петри.
- 67. Функциональные подклассы обычных сетей Петри.
- 1) Автоматные сети Петри
- 2) Маркированные графы
- 3) Сети свободного выбора
- 4) Правильные сети Петри