|
1 0 0 жаться в такое представление. В общем случае это приведёт к потере информации и, возможно, к тому, что некоторые свойства сетей Петри определить будет нельзя, но всё зависит от того, как представление будет получено. Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь Moiyr помочь пассивные маркировки маркировки, в которых нет разрешённых переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок это маркировки, ранее встречавшиеся в дереве. Такие дублирующиеся маркировки называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве маркировка (0,1,1), получившаяся в результате выполнения последовательности t2, /3, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности t2 из начальной маркировки. Для сведения дерева достижимости к конечному представлению используется ещё одно средство. Рассмотрим последовательность запусков переходов а, начинающуюся в начальной маркировке р и кончающуюся в маркировке р', р' > р. Маркировка р' совпадает с маркировкой р, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях, то есть р' = р+(р'-р) и (p'-vy) > 0. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность а можно запустить снова, начиная в р', приходя к маркировке р". Так как действие последовательности переходов а добавило р'-р фишек к маркировке р, она добавит также р'р фишек и к маркировке р', поэтому р" = р'+(р'-р) или р" = р+2(р'-р). В общем можно запустить последовательность с-п раз, получив в результате маркировку р+п (рр). Следовательно, для тех позиций, которые увеличивают число фишек по |
188 Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера. Заметим, что если какое-то представление бесконечного множества конечно, то бесконечное множество маркировок должно отображаться в такое представление. В общем случае это приведёт к потери информации и, возможно, к тому, что некоторые свойства сетей Петри определить будет нельзя, но всё зависит от того, как представление будет получено. Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки маркировки, в которых нет разрешённых переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок это маркировки, ранее встречавшиеся в дереве. Такие дублирующиеся маркировки называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве маркировка (0,1,1), получившаяся в результате выполнения последовательности //, /2, /$, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности /2 из начальной маркировки. Для сведения дерева достижимости к конечному представлению используется ещё одно средство. Рассмотрим последова 189 тельность запусков переходов <т, начинающуюся в начальной маркировке р и кончающуюся в маркировке р', р'>р. Маркировка //' совпадает с маркировкой р, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях, то есть р' = р+(р'-р) и (р!-у)>0. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность о можно запустить снова, начиная в р', приходя к маркировке р\ Так как действие последовательности переходов а добавило р'-р фишек к маркировке р, она добавит также р'-р фишек и к маркировке р\ поэтому р” = р'+(р'-р) или р” = р+2(р’-р). В общем можно запустить последовательность а-п раз, получив в результате маркировку р+п(р’-р). Следовательно, для тех позиций, которые увеличивают число фишек последовательностью сг, можно создать произвольно большее число фишек, просто повторяя последовательность а столько, сколько это нужно. В сети Петри на рисунке ..., например, можно запустить переход tj столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р2. Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа со, который обозначает «бесконечность». Для любого постоянного а определим со + а = со,а<со. со-а = со,со < со. Для построения дерева достижимости необходимы только эти операции над со. |