Cтраница 2
Для определения необходимого и достаточного условия безопасности нужно показать, что сеть Петри со свободным выбором покрывается объединением автоматных сетей Петри. [16]
С другой стороны, примитивная сеть может содержать места с разметкой со, поэтому она, в отличии от автоматной сети, может иметь бесконечное множество достижимых разметок и, следовательно, не моделируется конечным автоматом. В силу этого примитивная сеть может быть неограниченной, причем только в том случае, если содержит места с начальной разметкой со. [17]
Отсюда следует также, что автоматная сеть безопасна тогда и только тогда, когда ее начальная разметка содержит ровно одну фишку. Автоматная сеть жива тогда и только тогда, когда она представляет собой сильно связный граф, т.е. из любой вершины сети существует путь вдоль дуг в любую вершину, и ее начальная разметка содержит хотя бы одну фишку. [18]
В автоматной сети на рис. 4.3 ( автоматная сеть - частный случай свободной) имеются следующие тупики ( исключая тривиальный - множество всех мест): Rl р, Pi. РЗ Р Как видно, ни один из этих тупиков не содержит ловушки, поэтому сеть на рис. 4.3 не жива. [19]
Этот подкласс допускает и конфликты автоматных сетей Петри, и параллельность маркированных графов, но в более ограниченном виде, чем в обычных сетях Петри. [20]
В автоматной сети на рис. 4.3 ( автоматная сеть - частный случай свободной) имеются следующие тупики ( исключая тривиальный - множество всех мест): Rl р, Pi. РЗ Р Как видно, ни один из этих тупиков не содержит ловушки, поэтому сеть на рис. 4.3 не жива. [21]
Маркированные графы двойственны автоматным сетям Петри в теоретико-графовом смысле, поскольку в автоматных сетях Петри переходы имеют один вход и один выход, в то время как в маркированных графах один вход и один выход имеют позиции. Они являются двойственными также и с точки зрения моделирования. В автоматных сетях Петри легко представить конфликтные ситуации с помощью позиции с несколькими выходами, но нельзя моделировать создание и уничтожение фишек, необходимых для моделирования параллельности, или ожидания, свойственные задачам синхронизации. С другой стороны, маркированные графы могут моделировать параллельность и синхронизацию, но не могут моделировать конфликты или принятие решений, зависящие от данных. [22]
В частности, примитивные сети весьма похожи по своим свойствам на автоматные ( § 4.1, но не совпадают с ними. В примитивной сети каждый переход имеет ровно одно входное и одно выходное место, сеть консервативна. Графовая структура примитивных сетей более ограничена, чем у автоматных сетей, за счет ее регуляризации, получаемой при алгебраическом способе конструирования с помощью операций присоединения, исключения и итерации. [23]
Некоторые свойства автоматных сетей Петри очевидны. Прежде всего автоматные сети Петри - строго сохраняющие. Это означает, что число фишек в такой сети никогда не изменяется, и мы получаем таким образом конечную систему. Отсюда следует, что дерево достижимости для автоматной сети Петри является конечным, и, следовательно, все вопросы анализа для автоматных сетей Петри разрешимы. Фактически автоматные сети Петри эквивалентны автоматам, как они определяются в теории автоматов и формальных языков ( см. разд. Таким образом, эти модели имеют ограниченный интерес, несмотря на их мощность разрешения, из-за ограниченной мощности моделирования конечных автоматов. [24]
Некоторые свойства автоматных сетей Петри очевидны. Прежде всего автоматные сети Петри - строго сохраняющие. Это означает, что число фишек в такой сети никогда не изменяется, и мы получаем таким образом конечную систему. Отсюда следует, что дерево достижимости для автоматной сети Петри является конечным, и, следовательно, все вопросы анализа для автоматных сетей Петри разрешимы. Фактически автоматные сети Петри эквивалентны автоматам, как они определяются в теории автоматов и формальных языков ( см. разд. Таким образом, эти модели имеют ограниченный интерес, несмотря на их мощность разрешения, из-за ограниченной мощности моделирования конечных автоматов. [25]