4.4.  Темы для дальнейшего изучения

1.   Рассмотрите построение не дерева, а графа достижимости. Если вершина х порождает последующую вершину г с |і[г] — |і[г/] для некоторой неграничной вершины у, просто введите помеченную соответствующим образом дугу из х и у. Заметим, что путь из корня в вершину перестает быть единственным. Опишите алгоритм построения графа достижимости, покажите, что он сходится, и исследуйте его свойства, сравнивая с алгоритмом построения дерева достижимости.

2.   Дерево достижимости нельзя использовать для решения проблемы достижимости вследствие потери информации, порождаемой символом to. Он вводится, когда мы приходим к маркировке \і' и на пути от корня к ц' имеется такая маркировка ц, что |х' > |і. В этом

случае можно получить все маркировки вида р, + п(р' — р). Исследуйте возможность использования выражения а + b ■ п, вместо о, для того чтобы представить значения компонент. Если вы сможете определить дерево достижимости, в котором все векторы маркировок представляются выражениями, тогда решение задачи достижимости определяется просто решением системы уравнений.

3.   Обобщите определение сохранения, разрешая отрицательные веса. Что можно было бы считать разумной интерпретацией отрицательного веса? Является ли разрешимой задача определения сохранения сети Петри, если разрешены отрицательные веса?

4.   Разработайте с помощью матричного подхода к анализу алгоритм определения ограниченности сети Петри [61].

5.   Основная проблема матричного анализа—отсутствие информации

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

Для обоснования этого обозначим через сумму вектора запуска / по всем компонентам. Иначе говоря, если / = (Д, f2, » fm), то hf = /| + /2 + ... -f fm. Далее, если существует последовательность о, переводящая сеть Петри из маркировки р. в маркировку р\ тогда уравнение (4-1) имеет решение, являющееся вектором запуска Да) для а. Последовательность а можно определить из вектора запуска /(а) простым перебором всех возможных последовательностей длины 2ца), стараясь, чтобы каждая из них 1) была действительной и 2) приводила от р к р'. Для сети Петри с т переходами возможно самое большое т*~/ последовательностей длины

11.  На самом деле это число можно сократить. Поскольку нам известно, сколько раз запускается переход МА), сколько раз запускается t2 (/2) и т. д , то необходимо проверять не более чем 2у1 возможных упорядочений из запусков перехода /4, /2 запусков перехода t2 и т. д.

Это, казалось бы, обеспечивает процедуру решения задачи определения, является ли р' достижимой из р. Сначала решаем матричное уравнение р/ = р -f f • D. Если решения не существует, р/ недостижима из р. Если решение f существует, проверяем все 2 возможных упорядочений переходов. Если какая-нибудь из этих последовательностей действительна, то р' достижима из р, и мы имеем последовательность переходов, переводящую из р в р'.

Имеется только одно препятствие. Решение f может быть не однозначным, а (бесконечным) множеством векторов запусков, представленным множеством выражений (как показано выше для примера анализа сети Петри на рис. 4.27). Для определения возможности доказательства достижимости в этом случае необходимы исследования В простейшем случае может оказаться, что или все решения

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