Cтраница 1
Автоматная сеть Петри - это сеть Петри, в которой каждый переход может иметь точно один выход и один вход. [1]
Так как автоматная сеть ограничена, то ее граф разметок конечен, и, следовательно, в классе автоматных сетей разрешимы проблемы достижимости разметки, проблемы живости, проблемы Я-включения и Я-эквивалент-ности, проблема эквивалентности по языкам и все другие проблемы анализа свойств сетей. [2]
Некоторые свойства автоматных сетей Петри очевидны. Прежде всего автоматные сети Петри - строго сохраняющие. Это означает, что число фишек в такой сети никогда не изменяется, и мы получаем таким образом конечную систему. Отсюда следует, что дерево достижимости для автоматной сети Петри является конечным, и, следовательно, все вопросы анализа для автоматных сетей Петри разрешимы. Фактически автоматные сети Петри эквивалентны автоматам, как они определяются в теории автоматов и формальных языков ( см. разд. Таким образом, эти модели имеют ограниченный интерес, несмотря на их мощность разрешения, из-за ограниченной мощности моделирования конечных автоматов. [3]
В отличие от автоматных сетей синхрографы могут описывать параллелизм событий, но не допускают изображения конфликтных ситуаций. Основные свойства сетей, и в том числе живость и достижимость разметки, распознаваемы в классе маркированных графов, причем на основе простого анализа структуры графа и его начальной разметки. Структурные компоненты, в терминах которых формулируются условия ограниченности, живости и пр. Простой путь называется ( простым) циклом, если х1 хп. [4]
Машины на базе динамической автоматной сети строятся как многопроцессорные ВС. Элементом ВС является модуль. В системе имеются модули трех типов: вычислительный, коммутационный и интерфейсный. [5]
Маркированные графы двойственны автоматным сетям Петри в теоретико-графовом смысле, поскольку в автоматных сетях Петри переходы имеют один вход и один выход, в то время как в маркированных графах один вход и один выход имеют позиции. Они являются двойственными также и с точки зрения моделирования. В автоматных сетях Петри легко представить конфликтные ситуации с помощью позиции с несколькими выходами, но нельзя моделировать создание и уничтожение фишек, необходимых для моделирования параллельности, или ожидания, свойственные задачам синхронизации. С другой стороны, маркированные графы могут моделировать параллельность и синхронизацию, но не могут моделировать конфликты или принятие решений, зависящие от данных. [6]
Отсюда следует также, что автоматная сеть безопасна тогда и только тогда, когда ее начальная разметка содержит ровно одну фишку. Автоматная сеть жива тогда и только тогда, когда она представляет собой сильно связный граф, т.е. из любой вершины сети существует путь вдоль дуг в любую вершину, и ее начальная разметка содержит хотя бы одну фишку. [7]
В ряде случаев при определении автоматной сети накладывается дополнительное ограничение, чтобы ее начальная разметка имела ровно одну фишку. В то же время автоматные сети позволяют изображать конфликтные ситуации, когда одно и то же место-условие является входным ( или выходным) для нескольких переходов-событий. [8]
Заметим, что условия живости для автоматных сетей и синхрографов могут быть получены из теоремы 4.10 как следствия. [9]
Последовательная структура управления может быть представлена как связная автоматная сеть Петри ( см. § 4.2) с определенным топологическим ограничением, элементы которой интерпретируются специальным образом. [10]
Это непосредственно следует из конечности графа разметок любой автоматной сети. Этот граф представляет собой не что иное, как граф конечного автомата, в котором множество состояний образовано множеством достижимых в сети разметок, а алфавит - символами переходов сети. Поэтому на автоматные сети распространяются все результаты теории конечных автоматов, и изучать этот класс в рамках теории сетей Петри не имеет смысла. [11]
Охарактеризуйте класс сетей Петри, которые являются и маркированными графами, и автоматными сетями Петри. [12]
Маркированные графы двойственны автоматным сетям Петри в теоретико-графовом смысле, поскольку в автоматных сетях Петри переходы имеют один вход и один выход, в то время как в маркированных графах один вход и один выход имеют позиции. Они являются двойственными также и с точки зрения моделирования. В автоматных сетях Петри легко представить конфликтные ситуации с помощью позиции с несколькими выходами, но нельзя моделировать создание и уничтожение фишек, необходимых для моделирования параллельности, или ожидания, свойственные задачам синхронизации. С другой стороны, маркированные графы могут моделировать параллельность и синхронизацию, но не могут моделировать конфликты или принятие решений, зависящие от данных. [13]
Класс свободных сетей, как видно из его определения, строго включает классы автоматных сетей и синхронизационных графов, он является подклассом ординарных сетей Петри. Для этого класса Коммонером [27] и Хаком [41] были найдены необходимые и достаточные условия живости и безопасности. Они сформулированы с использованием следующих двух специальных типов подмножеств множества мест сети. [14]
Так как автоматная сеть ограничена, то ее граф разметок конечен, и, следовательно, в классе автоматных сетей разрешимы проблемы достижимости разметки, проблемы живости, проблемы Я-включения и Я-эквивалент-ности, проблема эквивалентности по языкам и все другие проблемы анализа свойств сетей. [15]