Ограниченность дерева достижимости в сетях Петри

Ограниченность дерева достижимости

Как видим, дерево достижимости можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемости . К сожаления, в общем случае его нельзя использовать

для решения задач достижимости и активности, а также для опре­деления возможной последовательности запусков. Решение этих задач ограничено существованием символа ω. Символ ω означает потерю информации; конкретные количества фишек отбрасываются, учитывается только существование их большого числа.

Рассмотрим, например, сети Петри на рис. 4.20 и 4.21, дерево достижимости которых изображено на рис. 4.22. Одно дерево достижимости представляет эти две схожие (но различные) сети Петри. Множества же достижимости их не совпадают. В сети Петри на рис. 4.20 число фишек в позиции р₂ всегда четно (пока не будет запущен переход t₁), тогда как в сети Петри на рис. 4.21 оно может быть произвольным целым. Символ t₀ не позволяет обнаруживать информацию такого рода, препятствуя использованию дерева до­стижимости для решения задачи достижимости.

Аналогичная трудность существует и для задачи активности На рис. 4.23 и 4.24 приведены две сети Петри, дерево достижимости которых изображено на рис. 4.25. Однако сеть на рис. 4.23 может иметь тупик (например, в результате последовательности t₁ t₂ t₃ )  а сеть Петри с рис. 4.24 — нет. Дерево достижимости же вновь не может передать различие этих двух случаев.

Вам также может быть полезна лекция "Методы проектирования защищенных информационных систем".

Заметим, что хотя дерево достижимости не обязательно содер­жит достаточную информацию для решения задач достижимости и активности, тем не менее в некоторых случаях это бывает возмож­но.

Сеть, дерево достижимости которой содержит терминальную вершину (вершину, не имеющую исходящих дуг), не активна (по­скольку некоторая достижимая маркировка не имеет последую­щих маркировок). Аналогично маркировка μ.' в задаче достижимос­ти может встретиться в дереве достижимости, и если это так, то она достижима. Кроме того, если маркировка не покрывается некото­рой вершиной дерева достижимости, то она недостижима.

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