Рекурсивные вложенные сети

Определение 1. Сетью будем называть набор N=(P, T, F), где P — конечное множество позиций, T — конечное множество переходов, PT=Ш; F (PЧT)(PЧT) — функция инцидентности.

Мультимножество m над непустым множеством S — это функция m: SN, где N — множество неотрицательных целых чисел. Числа {m (s)| sS} называются коэффициентами мультимножества, m (s) определяет число экземпляров элемента s. Множество всех мультимножеств над множеством S будем обозначать как S_MS.

Определение 2. Для произвольного элемента сети xPT через x и x обозначим мультимножества его входных и выходных элементов, такие что y (PT) x (y)=F (y, x), х (y)=F (x, y).

Определение 3. Пусть N=(P, T, F) — сеть, S — произвольное множество. Разметка M в сети N над множеством S есть функция из P в S_MS, ставящая в соответствие каждой позиции мультимножество над S. Размеченная сеть есть сеть вместе с некоторой разметкой, называемой начальной разметкой сети.

В этом определении элементы S (фишки) могут быть сложными объектами, например, сетями.

Пусть X — множество имен переменных и констант, интерпретируемых над некоторыми множествами. Определим язык Expr (X) выражений над X как множество выражений, построенных из элементов X при помощи операций объединения и умножения на натуральное число.

Через Var (expr) обозначим множество переменных, содержащихся в выражении expr.

Определение 4.

Для переменной xX, xExpr (X) и Var (x)=x;

Для константы xX, xExpr (X) и Var (x)=;

Если e₁, e₂Expr (X), то Var (e₁+e₂)=Var (e₁)Var (e₂).

Теперь мы переходим к определению рекурсивной вложенной сети Петри.

Определение 5. Пусть V — множество переменных, C — множество имен констант. Пусть = {l₁, l₂, …} - множество меток. Для каждой метки l определим парную ей метку, такую что =def l и множества и = def {| l} не пересекаются.

Структура рекурсивной вложенной сети Петри есть конечное множество сетей N₁=(P₁, T₁, F₁), …, N_k=(P_k, T_k, F_k), k1 (сеть N₁ называется системной, а сети N₂, …, N_k — элементными) такое, что для каждой сети N_i, i=1, …, k:

входные дуги переходов помечены выражениями из Expr (V), таким образом, что в любом выражении eExpr (V) имеется не более одного вхождения каждой переменной vV и для каждого перехода tT_i, для p, p't (pp') Var (E (p, t))Var (E (p', t))=, где E (p, t) обозначает выражение, которым помечена дуга (p, t);

выходные дуги переходов помечены выражениями из Expr (VC);

некоторые переходы в сети N_i помечены метками из .

Определим рекурсивно множество MarkedNets всех размеченных сетей из :

Обычную черную фишку будем рассматривать как маркированную сеть с пустой структурой;

MarkedNets={(N_i, f) | N_i, f: P_iMarkedNets_MS}.

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

Определение 6. Рекурсивной вложенной сетью Петри (RNP-сетью) будем называть структуру, в которой каждой константе cC поставлена в соответствие некоторая размеченная сеть из MarkedNets.

Разметкой RNP-сети называется разметка ее системной сети.

Размеченная RNP-сеть RNPN есть RNP-сеть вместе с некоторой ее разметкой (с конечным числом уровней вложенности), называемой начальной разметкой сети.

Определение 7. Пусть N_i=(P_i, T_i, F_i) — сеть в рекурсивной сети RNPN.

Означивание перехода tT_i есть функция b, приписывающая каждой свободной переменной v из выражений на инцидентных t дугах значение b (v) из множества MarkedNets.

Означенный переход есть пара Y=(t, b), где t — переход и b — означивание t.

Означенный переход Y=(t, b) является активным при разметке M в N_i, если pt E (p, t)(b)M (p).

Активный при разметке M означенный переход Y=(t, b) может сработать с результирующей разметкой M' (обозначается M [Y M'), где M'(p)=(M (p)E (p, t)(b))E (t, p)(b) для всех pP.

Для срабатывания M [Y означенного перехода M’Y=(t, b) мультимножество E (p, t)(b) размеченных сетей будем называть набором вовлеченных в это срабатывание элементных сетей.

Определим теперь шаг срабатывания в сети RNPN.

Определение 8. Пусть RNPN — RNP-сеть. Шаг в RNPN есть один из следующих двух видов срабатываний:

срабатывание непомеченного перехода в сети N_i (при некотором означивании), не меняющее разметки ни в сетях, являющихся элементами (фишками) N_i, ни в сети, в которой данная сеть N_i сама является фишкой (если таковая имеется), называется автономным шагом;

одновременное срабатывание перехода t с меткой l₁ в сети N_i и переходов t_k с меткой l₂, такой что = l₁, во всех непустых сетях из набора вовлеченных в это срабатывание элементных сетей (по одному переходу в каждой сети N_k) в соответствие с некоторым означиванием. Такой шаг называется синхронным.

Разметка M' достижима (непосредственно) от разметки M, что обозначается как MM', если существует шаг в RNPN, ведущий от M к M'.

Исполнение RNP-сети RNPN есть последовательность разметок M₀M₁M₂…, достижимых от начальной разметки M₀.