Ограниченность дерева достижимости
Ограниченность дерева достижимости
Как видим, дерево достижимости можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемости . К сожаления, в общем случае его нельзя использовать
для решения задач достижимости и активности, а также для определения возможной последовательности запусков. Решение этих задач ограничено существованием символа ω. Символ ω означает потерю информации; конкретные количества фишек отбрасываются, учитывается только существование их большого числа.
Рассмотрим, например, сети Петри на рис. 4.20 и 4.21, дерево достижимости которых изображено на рис. 4.22. Одно дерево достижимости представляет эти две схожие (но различные) сети Петри. Множества же достижимости их не совпадают. В сети Петри на рис. 4.20 число фишек в позиции р2 всегда четно (пока не будет запущен переход t1), тогда как в сети Петри на рис. 4.21 оно может быть произвольным целым. Символ t0 не позволяет обнаруживать информацию такого рода, препятствуя использованию дерева достижимости для решения задачи достижимости.
Аналогичная трудность существует и для задачи активности На рис. 4.23 и 4.24 приведены две сети Петри, дерево достижимости которых изображено на рис. 4.25. Однако сеть на рис. 4.23 может иметь тупик (например, в результате последовательности t1 t2 t3 ) а сеть Петри с рис. 4.24 — нет. Дерево достижимости же вновь не может передать различие этих двух случаев.
Вам также может быть полезна лекция "11. Методы и методики проектирования КСИБ".
Заметим, что хотя дерево достижимости не обязательно содержит достаточную информацию для решения задач достижимости и активности, тем не менее в некоторых случаях это бывает возможно.
Сеть, дерево достижимости которой содержит терминальную вершину (вершину, не имеющую исходящих дуг), не активна (поскольку некоторая достижимая маркировка не имеет последующих маркировок). Аналогично маркировка μ.' в задаче достижимости может встретиться в дереве достижимости, и если это так, то она достижима. Кроме того, если маркировка не покрывается некоторой вершиной дерева достижимости, то она недостижима.
Эти условия достаточны для решения некоторых задач достижимости и активности, но они не решают эти задачи в общем. Следовательно, для решения этих двух задач необходимы другие подходы.