МОДЕЛИРОВАНИЕ НЕДЕТЕРМИНИРОВАННЫХ ПРОЦЕССОВ С ДВОИЧНОЙ ЛОГИКОЙ ОГРАНИЧЕННЫМИ TS-СЕТЯМИ ПЕТРИ

Смирнова Е.И.

Новгородский государственный университет

  Процессы, протекающие в сложных интерактивных системах, слабо формализуются из-за своей недетерминированности. Это обстоятельство приводит к сложности аппарата, моделирующего логическую структуру процесса. В качестве инструмента для моделирования и исследования качественных характеристик динамических дискретных систем и процессов широко используется аппарат сетей Петри. Вместе с тем, классический аппарат сетей Петри не свободен от недостатков, ограничивающих возможности решения практических задач. Проблема может быть решена путем наложения некоторых ограничений на класс решаемых задач, что позволяет выделить из всего множества сетей Петри некий подкласс с дополнительными свойствами.
  Ограниченные TS-сети Петри, выделенные из множества сетей Петри и представленные в докладе могут быть использованы в системах с двоичной логикой, когда любой из компонентов системы либо влияет на ее состояние либо нет. Класс подобных задач достаточно велик: задачи моделирования динамических информационных процессов и, в частности, логическое моделирование гиперсегментных баз данных, задачи распределения ресурсов, моделирование различных интерактивных процессов. Часть задач принятия решения в теории управления динамическими процессами также могут быть сведены к подобным задачам.

Введем определения некоторых понятий.

Определение 1. Систему назовем управляемой системой с двоичной логикой, если система есть множество компонентов с различными характеристиками; каждый из компонентов находится в одном из двух состояний: активен или не активен; на множестве компонентов определено множество функций перехода от одного состояния к другому, каждая из которых зависит от некоторого системного события (внутреннего или внешнего). Если среди функций перехода есть зависящие от интерактивного воздействия, систему назовем интерактивно управляемой системой с двоичной логикой.
Определение 2. Состоянием или сценарием системы назовем набор активных компонентов =, где для , если состояние : активен. Переход от состояния к состоянию осуществляется скачком, посредством активизации другого набора компонентов.
  Процесс функционирования подобной системы является недетерминированным, поскольку заранее невозможно предсказать какой из наборов может быть активизирован в i-й момент времени. Этот процесс может быть формализован в виде концептуальной модели, построенной на базе теории сетей Петри^[1]. В основе этой модели лежит утверждение о том, что логическая структура определенной выше системы есть ограниченная сеть Петри =, где - множество позиций; - множество переходов, причем ; и - отображения , задаваемые матрицами инцидентности и , причем , если переход инцидентен позиции , , если позиция инцидентна переходу ; - начальная маркировка или разметка.
  В рамках данной модели множество компонентов системы есть множество позиций ; состояние системы определяется множеством активных компонентов; активному компоненту соот-ветствует помеченная позиция; активному множеству компонент - некоторая разметка ; множеству активных множеств - множество допустимых разметок; начальному множеству активных компонентов - начальная разметка ; - множество всех возможных перехо-дов от одного состояния системы к другому; смысл отображений и очевиден.
  Сформулированные и доказанные автором теоремы позволяют утверждать, что,
во-первых, задача определения достижимости некоторого перехода из множества переходов разрешима;
во-вторых, для того чтобы любой переход был достижим из разметки и разметка любой позиции была ограничена при функционировании сети (), достаточно выполнения условия
, где - логические функции конъюнкции, дизъюнкции и импликации соответственно, - элементы матриц инцидентности, причем расширенная матрица получена из матрицы путем дополнения строкой , где ;
в-третьих, всякую сеть, все переходы которой достижимы из разметки , можно представить позиционно эквивалентной из разметки сетью, у которой дерево достижимости совпадает с деревом достижимости исходной сети, а топология удовлетворяет условию достижимости любого перехода.
  Сказанное позволяет выделить из класса ограниченных сетей Петри подкласс, названный автором классом ограниченных TS-сетей Петри, обладающий некоторыми интересными свойствами.
  Для формального определения выделяемого класса введем следующие понятия.
Определение 3. Сценарием назовем помеченное подмножество вершин из множества : = , где , .
  Это означает, что в рамках предложенной модели сценарий однозначно определяется разметкой , которая есть двоичный n -разрядный набор, где вершина , если разметка 1, вершина , если разметка вершины 0.
  Сценарии связаны между собой символами-переходами. Система функционируя переходит от сценария к сценарию, причем возможность выбора очередного сценария зависит от набора вершин текущего сценария. Другими словами, сценарий , описывающий состояние системы в некий момент времени, подразумевает возможность посредством символа-перехода t перехода системы в другое состояние, описываемое сценарием . Переходов по сценарию может быть несколько, выбор любого из них зависит от действий пользователя, наблюдаю-щего на экране визуализированные элементы, но каждый из переходов однозначно переводит систему в состояние, соответствующее выбранному переходу.
Определение 4 (операция связывания сценариев). Сценарий назовем связыва-емой через переход со сценарием , если некоторое подмно-жество , состоящее из вершин, входящих в сценарий : = инициализирует активизацию некоторого подмно-жества вершин, входящих в сценарий : .
Определение 5. Сеть, порожденную связыванием посредством перехода сценария со сценарием , которые определены на множестве всех допусти-мых сценариев, назовем примитивной ограниченной ТS-сетью, для которой функции инцидентности формируются следующим образом:
  Начальная разметка : 1, если , и 0, если .
Замечание. Для любого множества сценариев, определенного на множестве допустимых информационных элементов, такие, что , где , но , если .
Определение 6. Ограниченные сети Петри, порожденные множеством символов-переходов Т на множестве сценариев S, назовем ограниченными TS-сетями Петри.
  Выделенный класс ограниченных TS-сетей обладает рядом свойств, главными из которых являются следующие.
Свойство 1. В ограниченной TS-сети Петри для , разрешенного в рамках сценария , выполнены два условия:

1. все вершины, составляющие сценарий и определяющие срабатывание перехода , либо являются размеченными изначально, либо существует хотя бы один другой переход такой, что вершины приобретают разметку все одновременно в результате срабаты-вания этого перехода .

2. разметка , определяющая сценарий , совпадает с вектором-столбцом матрицы , соответствующим переходу : . Причем возможно существование другого, отличного от , перехода : , где .

Это означает, что ограниченная TS-сеть в процессе функционирования переходит от состояния к состоянию в результате последовательного срабатывания цепочки переходов. Смена состояний системы обуславливает смену сценариев: все фишки, пометившие вершины сценария в результате срабатывания перехода перейдут к вершинам сценария в результате срабатывания разрешенного в рамках сценария перехода .
Свойство 2. Очевидным следствием свойства 1 является то, что ограниченные TS-сети Петри в качестве подкласса в ходят в множество ограниченных сетей Петри, поскольку количество фишек, помечающих вершину, не может быть больше 1.
Свойство 3. Ограниченные TS-сети являются подклассом классических сетей Петри, обладающих свойством k-ограниченности, при k=1, но свойство это не является ограничением накладываемым принудительно на топологию сети, как в ограниченных сетях Петри, а является именно свойством, приобретенным благодаря особой структуре TS-сети (свойство 1).
Свойство 4. Ограниченные TS-сети в силу уже отмеченного свойства топологии обладают еще одним замечательным свойством, вытекающим из теоремы о достаточном условии достижимости переходов ([1], теорема 2). В силу указанной теоремы TS-сеть является живой сетью, если в ней есть хотя бы один переход, который может сработать из начальной разметки. Для ограниченной TS-сети условие теоремы выполняется для любого множества элементов, названного сценарием, и для любого перехода, разрешен-ного в рамках соответствующего сценария, если какой-либо сценарий из допус-тимого множества определен (размечен) как начальный.
Свойство 5. Множество переходов в ограниченной TS-сети Петри есть множество, динамически формируемое в процессе конструирования или в процессе формирования структуры сети. Но множество это конечно, поскольку определяется бинарным отношением , где - сценарии из допустимого множества сценариев , . Бинарное отношение является подмножеством декартова произведения множества само на себя: . Отсюда следует конечность множества , поскольку , где . Тогда .
Выделенные свойства ограниченных TS-сетей Петри, позволяют использовать их в качестве основы для адекватного аппарата моделирования динамических недетерминированных структур и процессов. Кроме того, поскольку ограниченные TS-сети Петри являются подклассом классических сетей Петри, операции над ними легко описываются с помощью теоретико-множественных операций.
Предложенный автором аппарат ограниченных TS-сетей Петри позволяет построить алгебру для адекватного логического моделирования динамических недетерминированных структур и процессов. В данном исследовании обосновано выделение класса сетей, обладающих некоторыми специальными свойствами, существенными для класса рассматриваемых задач. Эти свойства позволяют определить набор операций для конструирования корректных сетей из подсетей и примитивов и проведения предварительного анализа получаемых сетей, что, в свою очередь, дает основу для аппарата моделирования логической структуры и управления процессами в динамических недетерминированных системах. В работе^[2] подробно изложены основы построения алгебры ограниченных TS-сетей Петри в приложении к задачам логического моделирования гиперсегментных баз данных с изображениями.

ССЫЛКИ

1. Emelyanov G.M., Smirnova E.I. Logical Model Of Hypertext Image Database // Pattern Recognition and Image Analysis.-1999.-Vol.9, № 3. - pp.485-491.
2. Emelyanov G.M., Smirnova E.I. Logical Simulation Algebra of Hypertext Image Database // Pattern Recognition and Image Analysis.-2000.-Vol.10, № 1.

СВЕДЕНИЯ ОБ АВТОРЕ.

Смирнова Елена Игоревна - Новгородский государственный университет, Россия , 173003, г. Великий Новгород, ул. Б.С.-Петербургская, 41. Доцент кафедры программного обеспечения вычислительной техники, кандидат физико-математических наук

Контактные данные:

Россия , 173003, г. Великий Новгород, Григоровское шоссе, д.33, кв. 53, тел. 2-79-40
E-mail: shi@novsu.ac.ru