Книжка по сетям Петри, страница 6

Например, для места р, в сети на рнс. 2.1 сущестВУЕт Г = )рты ГДЕ Х вЂ” ПУСТОЕ СЛОВО, таКОЕ, Чтп р,' с, 4 (Ме =(1,0,0,0! [г, )М, (1.1,0,0))Л (М~ > Мс ) Л (Муз ) = 1 ) Мс (Рз! = 0). [э Рч Однако место рч не ограничено по другой Рис. 2.1, причине, так как нельзя найти пару достижи- 22 1од,о 1що,о О.ОбсО б) Рис. 2.2. мых в атой сети Разметок М, и М, таких, что (Мз > М1) Л (Из (Рб) > > М1 (Рч) ), хотя и ясно, что последовательности срабатываний вида г",г,г" ,ведут к накоплению любого числа и фишек в Рч. Можно отметить слеДУющУю разницУ в неогРаниченности мест Рз и Рч.

в Р, может быть "бесконечное" число фишек, а в р4 — сколь угодно большое, но конечное число фишек, так как переход г, может сработать только конечное число раз, не большее, чем число срабатываний перехода г,. Таким образом, неогРаниченность места Рч "втоРична" по отношению к неогРаниченности места Рз. Выше, в % 1.2. было дано определение графа разметок сети Петри, ха.

рактеризующего динамику ее функционирования. Исследование проблемы ограниченности сводится к анализу графа другого типа, а именно — покрывающего дерева сети. Для любой сети такой граф конечен и может быть построен с помощью следующей процедуры: 1) Первоначально предполагается, что дерево содержит единственную вершину-корень Мо и не имеет дуг. 2) Пусть М вЂ” вершина дерева, которая еще не объявлена листом (т.е. вершиной, из которой не исходит ни одна дуга), но в дереве нет исходящих нз нее дуг.

Возможны четыре случая. а! Ни один из переходов сети не может сработать при разметке М, т.е. 'Фг Е Т: М,"и У(г). В зтом случае вершина М объявляется листом. б) На пути нз корня дерева в вершину М существует вершина М такая, что М = М . Вершина М объявляется листом. в) На пути из корня дерева в вершину М существует вершина М такая, что М ( М. Для любого места р такого,что М (Р! < М(р), значение, соответствующей координаты И заменяется на ш и вершина И объявляется ш листом. г! Если нн один нз вышеперечисленных случаев не нмвет места, то М— внутренняя вершина дерева.

Для каждого перехода г Е Т такого. что М ~ Э Р (г), в дерево добавляется новая вершина М' = М вЂ” Р (г) + Г (г) н дуга, ведущая из М в М, помеченная символом г. На рис. 22,а показано покрывающее дерево для сети Петри, изображенной на рис. 1.3, а на рис. 2.2, б — дпя сети на рис. 2.1. Из правил построения покрывающего дерева для сети Петри следует, что вершины дерева представляют собой векторы из множества (ч" (ч Х...

Х (ч', где и — число мест в сети. Введем несколько олределе- и ний и отметим некоторые свойства множеств и последовательностей векторов из Й" и й„",. Для отношения частичного порядка <множество й(" является решеткой, а множество й„, является полной решеткой [13) и любое 23 подмножество Х С й" имеет единственную наимаиыиую верхнюю грань УЕ К",„: (Ъ~Е ЕХ: (Е < У))ЛЧУ'Б й"„: ()ГЕ ЕХ: (Е <У)'ь(У< У Л. Цепью С в йп называется последовательность (Е, Ез,... ) такая, что тт) > 1, )у!' Э 1: Е, < Ег+1 ЛЕ~ чь Е;. МножествоХЕ йпы замкнуто,если любая цепь в Х содержит свою наименьшую верхнюю грань.

Поскольку й" — полная решетка, любая цепь в й,"., замкнута, в то время как бесконечные цепи из й" не содержат своих наименыиих верхних граней. Множество ХС.К" монотонно, если Ю Е Е Х, УЕ Е й,"„: Е < Е ы Е Е Х. Для множества Х Е й",„его множество максимальных элементов определяетсл как (ЕЕХ) )(ЭЕ ЕХ: Е'лЕЛЕ ФЕ),'. Для множества Х ь. Кп его замыканием называется наименьшее замкну.

тое множество из й,"„, содержащее Х. Л е м м а 2.1. Любое бесконечное подмножество множества й,н содвр. зги т бес конвчк ую цепь. До к а зете л ь ст во. Любая бесконечнап цепь из й,п содержит бвско. печную неубывающую последовательность. Любое бесконечное подмножество множества й„, можно упорпдочить так, чтобы оно не содержало одинаковых векторов. Из полученной бесконечной последовательности выбирается бесконечная подпоспедовательность так. чтобы все первые координаты векторов следовали в неубывающем порядке. Из этой подпоследовательности выбирается такая, что асе вторые координаты следуют в неубывающем порядке, и т.д. для всех и координат. Результатом являетсп бесконечнап последовательность, не убывающая в каждой координате и не содержащая одинаковых векторов.

Г) Л е м м а 22. Любое множество взаимно несравнимых (по опюиюкиям <, >, ) векторов иэ й,"„колвчло. Д о к а з а т е л ь с т в о. Из леммы 2Л следует, что любая бесконечная цепь е множестве й" состоит из разных сравнимых по упомянутым отношениям векторов. Следовательно. множество несравнимых векторов должно быть конечным. П Т е о р е м е 2.1.Для пюбоб сети )У вв покрывающее дерево конечно. До к а з а т ел ь с т во. Предположим, чтодеревобесконечно.

Попостроенню, из каждой его вершины может исходить дуг не больше, чем чис. ло пе)юходов в сети, которое конечно. По лемме Кбнига [56) в дереве должен существовать бесконечный путь, начинеющился в корме. По лемме 2.1 должна существовать бесконечная цепь векторов.рвзметок, представляющая собой подпоследоватепьность этой цепи, а в ней существуют две разметки М и М такие, что М предшествует М по дереву и М> М.

Но, по построению дерева, вершине М должна быть листом, что противоречит предположению о бесконечности выбранного пути. Т е о р е м а 22. Проблема ограниченности сети Патри разрешима. До к а з а т е л ь с т в о. Поскольку для любой сети д) покрывающее дерево конечно, описанная выше процедура его построения эффективна, т.е. может быть выполнена за конечное число шагов. Если дерево содержит лист с разметкой М. содержащей ы, то сеть не ограничена.

Действительно, в этом случае существуют, по построению, внутренняя вершина М и подпоспадоветепьность срабатываний г такие, что (М'[г> М) Л(М> М'1. Подпоследовательность г может повторяться сколь угодно болыиое число рэз, порождая последовательность возрастающих разметок. Если жа дерево ме содержит вершим-разметок с символом ьс, то для каждой его вершины М, отличмом от тупиковой, существует переход с Е Т и другая вершина М такая, что М чь М и М[с ) М . Учитывая, что М Мр принадлежит гт ((У[, убеждаемся, что разметка из г( (ЛЦ представлена в дерева.

Так как дерево конечно, то число достижимых в сети разметок конечно и соответственно каждая из разметок представляет собой вектор из "конечных" чисел. Таким образом, алгоритм распознавания ограниченности сати состоит в построении ее покрывающего дерева и последующего просмотра конечного числа вершин-разметок. Если будет найдена хотя бы одна разметка с символом ш, то сеть не ограничена, в противном случае — ограничена.

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

22,6 символ ьс появляется только в позиции, соответствующей месту рз сети на рис. 23, но нет символа ьь соответствующего месту р». Поэтому с помощью алгоритма распознавания ограниченности мз теоремы 2.1 нельзя установить, какие места сети могут иметь "вторичную" неограниченную разматку. Чтобы иметь такую возможность, следует построить полное локрыеалхиее дерево сети по следующей процедуре. 1. Строится покрывающее дерево сети д(.

Если это дерево не имеет ьслистов, то построение полного дерева закончено и оно совпадает с покрывающим деревом. 2. Если покрывающее дерево содержит ш-лист М, то для него строится покрывающее дерево для сети дс, полученной из д( заменой начальной раз. метки Ме на разметку М.

При этом правила срабатывания переходов и изменение разметки сети обобщаются на случай векторов с ш с учетом арифметических свойств расширенного множества натуральных чисел (см. % 121. Построенное дерево присоединяется к основному дереву совмещением корня М в новом дереве с листом М в основном дерева. Процесс повторяется до тех пор, пока не исчезнет последний со-лист. На рис. 2.3,а показано полное покрывающее дерево для сети, изображенной на рис. 1.3, на рис.

2.3,6 — для сати на рис. 2.1. В перв(эм случае полное дерево ме Лает новой информации по сравнению с покрывающим деревом, так (»ак сеть на рис. 1З имеет единственное неограниченное место'"первого рода". Во втором случае в полном дереве символ ьг пояшшется в позиции места р», неограниченного места "второго рода".

Т е о р е м а 2.3. Проблема ограниченносги некогорого места е произвольной сети Петри разрешима. Д о к а з а т ел ь с т в о. Из построения полного покрыеаощего дерева дле сети (У легко устанавливается, что это дерево конечно. Произвольное место р не ограничено, если и только если среди вершин полного дерева существует вершина М такая, что в мознцин места р стоит символ ги.

Действительно, как следует из доказательства теоремы 2.1, в покрывающем дере- ве сети Д) для любой его вершины М существует в замыкании множества Я (И) разметка М такая, что М > М. По построению полного дереве, зто свойство сохраняется для всех его вершин, С другой стороны, если зафиксирована произвольная разметка М Е Е В (В», то в полном покрывающем дереве есть вершина с разметкой М > Э М . Из определения неограниченности места р следует, что оба неравенст. ва имеют места только в том случае, если хотя бы одна из вершин полного дерева содержит гс в позиции места р. ):) Т е о р е м а 2.4.