Бисимуляция ресурсов в сетях Петри

• Автор: Башкин, Владимир Анатольевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Ярославль
• Количество страниц: 145 с.

Оглавление
Введение

1. Сети Петри и бисимуляция разметок

1.1. Множества, отношения, мультимножества

1.2. Системы помеченных переходов, бисимуляции

1.3. Сети Петри

2. Бисимуляция ресурсов в обыкновенных сетях Петри

2.1. Конечное представление отношений

2.1.1. Базисы отношении.

2.1.2. Конечность базиса Л Гзамыкания

2.1.3. Свойства основного базиса

2.2. Подобие ресурсов
2.2.1. Определение подобия
2.2.2. Свойства.
2.2.3. Неразрешимость.
2.3. Условное подобие ресурсов.
2.3.1. Определение условного подобия
2.3.2. Свойства.
2.3.3. Полулинойность множества пар подобных ресурсов
2.4. Бисимуляция ресурсов
2.4.1. Определение бисимуляции
2.4.2. Слабое свойства переноса
2.4.3. Проверка бисимулярности отношения .
2.4.4. Построение аппроксимации максимальной бисимуляции ресурсов.
2.5. Редукция сети на основе подобия ресурсов
3. Бисимуляция ресурсов в сетях с невидимыми переходами
3.1. Сети Петри с невидимыми переходами
3.2. Подобие и бисимуляция ресурсов в сетях с тпереходами .
3.3. Насыщенные сети Петри.
3.4. грбисимуляция ресурсов.
3.5. Алгоритм построения аппроксимации
4. Бисимуляция ресурсов в сетях Петри высокого уровня
4.1. Сети Петри высокого уровня
4.2. Раскрашенные сети Петри
4.3. Элементарные ресурсы.
4.4. Подобие и бисимуляция ресурсов в раскрашенных сетях . .
4.5. Алгоритм построения аппроксимации .
5. Бисимуляция ресурсов во вложенных сетях Петри
5.1. Вложенные сети Петри
5.2. Объектные ресурсы
5.3. Системные ресурсы
5.4. Системноавтономные ресурсы .
5.5. Рекурсивные вложенные сети Петри.
Заключение
Список литературы


Основное внимание при этом уделяется проблеме разрешимости определяемого отношения и алгоритмам нахождения бисимуляционно эквивалентных ресурсов для заданной сети Петри. Исследование свойств и структуры отношения подобия ресурсов и других отношений эквивалентности на множестве ресурсов обыкновенной сети Петри, сохраняющих наблюдаемое поведение системы. Исследование разрешимости этих отношений и построение со-о тветст ву ющих ал гор и тмов. Исследование бисимуляции ресурсов в сетях Нсгри с невидимыми переходами (когда срабатывание некоторых переходов не видно наблюдателю) и построение соответствующих алгоритмов. Определение и исследование бисимуляции ресурсов для сетей с индивидуальными фишками — сетей Петри высокого уровня и вложенных сетей Петри. Разработка алгоритмов редукции сети Петри на основе бисимуля-ционной эквивалентности ресурсов. Основные результаты. Введено понятие ресурса сети Петри. Определено отношение подобия ресурсов сети Петри, сохраняющее бисимулярность разметок, исследованы его свойства. В частности, доказано, что подобие ресурсов обладает конечным базисом относительно аддитивного транзитивного замыкания и в то же время неразрешимо. Определено отношение условного подобия ресурсов сети Петри, исследованы его свойства. Доказано, что множество нар подобных ресурсов полулинейно, причем в качестве базиса разложения могут использоваться пары условно подобных ресурсов. Определено отношение биепмуляиии ресурсов сети Петри, исследованы его свойства и взаимосвязь с подобием ресурсов. Показано, что бисимуляция ресурсов является сужением подобия ресурсов. Построен алгоритм проверки того, является ли данное отношение на множестве ресурсов бисимуляцией. Получен алгоритм построения для заданной обыкновенной сети Петри отношения бнеиму-лянии на множестве ресурсов размера не больше заданного, т. Петри. Сформулированы правила построения редуцирующих преобразовании обыкновенных сетей Петри на основе подобия ресурсов. Структура работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. В первой главе диссертации приводятся общие определения из теории мультимножеств, теории бисимуляций и теории сетей Петри. Во второй главе приводятся результаты о способах задания бесконечных отношений на мультимножествах при помощи конечных базисов. Доказывается, что любое аддитивно и транзитивно замкнутое отношение на множестве мультимножеств обладает конечным базисом. Приводится структура одного такого конечного базиса, названного основным базисом. Доказывается ряд его свойств, приводятся алгоритм проверки принадлежности данной пары мультимножеств замыканию основного базиса и алгоритм построения основного базиса отношения по любому другому конечному базису. Вводятся понятия ресурса сети Петри как мультимножества над множеством позиций сети. Вводится понятие подобных ресурсов. Два ресурса подобны, если в любой разметке мы можем заменить один из них на другой, и при этом дальнейшее наблюдаемое поведение сети не изменится (в смысле бисимуляционной эквивалентности поведений). Исследуются свойства подобия ресурсов — отношения на множестве ресурсов сети Петри, состоящего из всех пар подобных ресурсов. Доказывается, что подобие ресурсов является отношением эквивалентности, замкнутым относительно сложения. Оно обладает конечным базисом относительно аддитивного транзитивного замыкания. Доказывается, что корректное слияние позиций [) является сужением подобия ресурсов, состоящим из пар ресурсов единичной мощности. Из этого следует неразрешимость подобия ресурсов для случая обыкновенных сетей Петри. Вводится понятие условного подобия ресурсов, исследуются его свойства. Доказывается теорема о нолулинейности множества пар подобных ресурсов. Вводится понятие бисимуляции ресурсов. Описываются его свойства, взаимосвязь с подобием ресурсов, приводятся алгоритм проверки бисимуляции ресурсов с использованием слабого свойства переноса и алгоритм построения аппроксимации максимальной бисимуляции ресурсов. Рассматриваются способы редукции обыкновенных сетей Петри на основе подобия (бисимуляции) ресурсов.