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

Поскольку в пустоы цикле этот переход мертв, то и все остальные переходы пустого пути, начинаемцегося в пустом цикле, мертвы. Для любого перехода в синхрографе можно выписать следующее мне. жество всех простых путей (в том числе циклов): (1 ! каждый путь или заканчивается этим переходом или является циклом, содержащим этот переход, (2) ми один из путей не является подпутем другого пути из этого множества, (3) каждый путь, если зто не цикл, начинаетсп некоторым переходом, который нпн не имеет входных мест или принадпежит некоторому циклу.

Если переход потенциально живой, то все переходы из построенного множества путей также потенциально живы. Зто имеет место только тогда, когда каждый путь из этого множества обладает одним из следующих свойств: 1! он начинается переходом без входных мест (этот переход всегда может сработать), 2) рн начинается в цикле, содержащем хотя бы одну фишку прм Ме, 3) он является циклом, содержащим хотя бы одну фиц»ку при Ме.

Поэтому, если переход является потенциально живым, то он не может принадлежать пустому прн Ме циклу или пустому при Ме пути из такого цикла. С) В синхрографе на рис. 4.4,в потенциально живыми являютсп переходы г», г,», мер»вымя переходы г», г». Т е о р е м а 4.6. Синхрозрвф является живым, если и только если любой цикл в нем яе пуст при начальной разметке Ме. Д о к аз а тельство. При выполнении условмя теоремы любой переход в сннхрографе является потенциально живым, так как дпя наго вы. полнены условия теоремы 4.5.

При функционировании смнхрографа ни один из циклов не может стать пустым, поэтому условияттеоремы 4.6 вы. полнены для любой достижимой разметки и. следовательно. любой из переходов сети является живым, вся сеть — жива. Если сннхрограф является живой сетью, то он не может содержать пустых при Ме циклов. так как в этом случае переходы пустого цикла будут метрвыми. П Синхрограф на рис. 4А,а не является живым, так как он содержит пустой цикл (т», р», г», рч, г»! .

В синхрографе на рис. 4 4,6, отличающемся от предыдущего начальной разметкой, все циклы непусты, поэтому сн живой. В то время как любая автоматная сеть ограничена, сннхронизацнонная сеть может содержать неограниченные места, как, например. сеть на рнс. 4.6, в которой таким местом является место рз. Распознавание ограниченности И и безопасности синхраграфов может быть выполнено так же, как и в общем случае сетей Петри (теоремы 2.3 и 2.6 главы 2), но для живых синхрографов про.

верку на ограниченность и безопасность можно оде. пать на основе анализа их структурных свойств и начальной разметки. Т е о р е м а 4.7. Живой синхрограбс лвпнвтсп ограниченным, если и только если кал))ое его место входит в нвкоторый цикл. Д о к а з а т е л ь с т в о. Если место р вхсщмт в д цикл синхрографа, то максимальное число фишек. Рис.

4.5. которое может в нем накопиться, не превышает об. щего числа фишек в этом цикле, а ано постоянно (теорема 4.4), следовательно, место р ограничено. Если место р не входит ни в какой цикл,то оно принадлежит некоторо. му пути, который начинается или переходом без входных мест или переходом в некотором цмкле. В обоих случаях переход с = р и переход С = р живы, так как жива сеть. При этом число срабатываний перехода с не зависит от числа срабатываний перехода с, так как они не входят в некоторый цикл.

Поэтому возможна такая последовательность срабатываний, в которой с срабатывает сколь угодно 66льшее чиссю раз, чем с'. и, следовательно. место р неограничено. С) В живом синхрографа на рис. 46 место рэ не ограничено, так как оно не входит ни в один цикл. В живом синхрографе на рис. 4.4.6 все места огра. ничены и он ограничен, так как выполнено условие теоремы 4.7.

Т е о р е м а 4З. Живой синхрограф безопасен, если и только воли каждое вго место входит в некоторый «икп, содержащий ровно одну Фишку. До к а за т ел ьств о. Следствиеизтеоремы47. П Проблема достижимости разметки разрешима в классе синхрографов, так как она эквивалентна проблеме живости (теорема 2Л4), а последняя разрешима в этом классе (теорема 4.6) . 4 43. Свобадлые сетя Свойоднап сеть (или сеть со свободным выбором) — зто сеть Петри (р, Т, Е, Ме) такая, что ч(р,с) Е Е: р' (с)ус =(р), т.е. любая дуга, ведущая от места к переходу, или начинаетсл местом, из которого не выхо. дит ни одной другой дуги„илм заканчивается переходом, в который не ведет никакая другая дуга. Пример свободной сети показан на рис.

4.6,д В свободной сети каждое конфликтное место [место, из которого выходит более чем одна дуга! является входным для такого множества перахадов, в катарам при любой разметке любой (но адин) из переходов может сработать мли все песюхады не могут сработать. Например, в сети на рис.

43.6 множество переходов (с,, С, ), которые имеют в качестве входного места конфликтное место р„ не удовлетворяет таким условиям, так как после срабатывания переходе сэ переход сс не может сработать. Эта сеть не является свободной. Класс свободных сетей. как видно из его определения, строго включает классы автоматнсих сетей и синхронизационных графов, он являетсл под. классом ординарных сетей Петри. Для этого класса Коммонером (271 и Хаком (41! были найдены необходимые и достаточные условия живости и безопасности.

Они сформулированы с использованием следующих двух специальных типов подмножеств множества мест сети. 42 Рис. 4.т Ловушкой называется непустое подмножество 0 1, (Оы ..., дч) множества мест Р такое. что 0' ь О, й где 0 ' ).) 41, а 0 1.) о1. р, й Я Другими словами, любой пе- Янс. 4.6. реход, входное место которого принадлежит О, содержит в 0 и некоторое своа выходное мшто. Когда такой пере.

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

не содержит ми одной фишки, то этот переход мертв. Пустой тупик остается пустым при функционировании сети, так как разметка мест в тупике не может возрастать. Заметим. что ловушка и тупик не исключают друг друга. В сильно связной сети мнвхество Р всех ее мест обладает свойством Р Р, т.е. является одновременно ловушкой н тупиком. В сети на рис. 4.7 множество мест 0 =( ры рэ ) образует ловушку, так как 0' (гэ, тэ), 0 = (г„)э, гз) и, следовательно. 0 С О. Множество мест В (р„ра) образует тупик, так как Я (га,га), В (га,гт,г,) и 'ВСЯ . Критерий живости свободной сети основан на следующих рассуждениях.

Как отмечено вьмие, переход, содержащий выходное место в тупмке, не сможет сработать, если тупик пуст. Таким образом, сеть, при функционировании которой мекоторый тупик может оказаться пустыМ, не будет живой. Чтобы удержать фишки а тупике нужно, чтобы тупик содержал размечемную ловушку. Прежде чем оформить зто рассуждение в теорему. докажем две вспомогательные леммы. Дпя сети с множеством мест Р и для разметки М обозначим через Ре )М) множество мает (р е Р) м(р) О), т.е. множество мест без фишек при разметке М, а через Р'(М) -множество(рЕР) М)р) )0),т.е.

множество аеаст, содержащих Фишки при М. Л е м м а 4.1.Дол произвольного подмножества переходое 8 в сети Легри и для произвольной разметки М, если ('8 Г1 Ре)МП ь. 8, то или в 8 существует переход, могуилтй сработать при М, или существует пустой при М тупик Я такой, что 8 С В, Д о к а з ат ель с т во. Предположим,что выполнено условиелеммы и в 8 наг перехода, могущего сработать при М, т.е. 'у с Е 8: с ф Р'(М), или что то же самое, \с с е 8: 'с гт Ре(м) чь Ф или)г с е 8: с е ( с гт Рэ(м!)'. Отсииса следует, что 8 ь.

('8 Гт РЕ (М) ) . По условию леммы ( 8 Г1 РЕ(М))' С ь.8, поэтому ('8 Г1ре(М) ) — пустой тупик. О Л е м м а 42. Пусть в свободной сети Петри (Р, Т, Е, Мс) достижима разметке М, а 8 ь. Т вЂ” множество переходов, мертвых при М. Тогда сушествувг достижимая от М резмэтка М и пустой при М тупик Я такой, что 8 С Я'. Д о к а з а т е л ь с т в о леммы проводится индукцгюй по мощности множества 8. Если 8 содержит все переходы сети, то непосредственно применима лемма 4.1. Это базис индукции. Каждый шаг индукции связан с уменьшением числа переходов в 8.