Начальная маркировка

Cтраница 2

Эти три определения, по существу, одинаковы. Разумеется, определение начальной позиции является частным случаем определения начальной маркировки, а оно - частным случаем определения множества начальных маркировок. [16]

Далее вводятся еще одна позиция s, и два новых перехода, tA и tB - Начальная маркировка всей сети ( включая Л и В как подсети с общими позициями; позиции ГА, ГБ и s; переходы tA и tB) определяется одной фишкой в s и нулем в остальных. Переход tA имеет в качестве входа s, а выход его порождает начальную маркировку сети Л плюс фишку в ГА; переход tB в качестве входа также имеет s, а выход его создает начальную маркировку сети В плюс фишку в гв. [17]

Мы допускаем, что начальная маркировка безопасна. Заметим, что такая принудительная безопасность возможна только для позиций, которые в начальной маркировке являются безопасными и входная и выходная кратность которых равна 0 или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следовательно, не может быть безопасной. [18]

Из этих определений легко видеть, что системы сложения векторов и сети Петри эквивалентны. По данной сети Петри мы можем построить систему сложения векторов, начальным вектором которой является начальная маркировка, а базисные векторы взаимно однозначно соответствуют переходам. N компонент векторов системы сложения векторов соответствуют маркировкам п позиций сети Петри или ( в случае базисных векторов) изменениям, происходящим из-за запуска соответствующего перехода. [19]

Таким образом, к числу основных задач анализа Г - сетей относятся задачи проверки ограниченности ( безопасности) и определения соответствующего k, сохранения или строгого сохранения, активности и достижимости. Эти задачи могут рассматриваться в двух постановках: проверка выполнения заданного свойства для Г - сети с данной начальной маркировкой ц0; определение условий ( например, в виде множества возможных начальных маркировок), при которых заданное свойство Г - сети выполняется или не выполняется. [20]

Многие из первых исследователей не давали формального определения своих моделей, а описывали неформально относящиеся к их работе компоненты, такие, как позиции, переходы, фишки и правило запуска. Одно из первых формальных определений было дано Патилом [231] в его докторской диссертации, в которой сеть Петри определялась в виде четверки ( Т, Р, Л, В), где Т - множество переходов, А - множество дуг, Р - множество позиций и В - начальная маркировка. [24]

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

Однако это определение имеет несколько модификаций. Другое, более общее определение допускает множество начальных маркировок вместо одной маркировки. [26]

Более общим является понятие достижимых маркировок. Непосредственно достижимые маркировки являются также и достижимыми. Множество достижимости Л ( ц0) Г - сети с начальной маркировкой UQ - это множество всех достижимых из ц0 маркировок. [27]

Наша следующая задача - показать, что задача достижимости нуля сводится к задаче достижимости нуля в одной позиции. Доказательство этого утверждения также основано на вспомогательном построении. Пусть дана сеть Петри d ( Pi9 7, Л, 0) с начальной маркировкой ( А. [28]

Трансформации в этих вершинах реализуют подачу на вход автомата соответствующего символа. Аналогично выходным символам соответствуют вершины, сгруппированные в блок О; трансформации в нем реализуют выдачу символов на выходе автомата. Вершины блока Т соответствуют переходам автомата, состояниям автомата соответствуют входные и выходные позиции этих вершин. Начальная маркировка Г - сети моделирует начальное состояние автомата. [29]

Представление сетью Петри программы на, полученное из блок-схемы на. [30]

Страницы: 1 2 3