Главная » Файлы » Тезисы участников конференции

Бисимуляции и автоморфизмы сетей Петри

[ Download from this server (66.5Kb) ]
БИСИМУЛЯЦИИ И АВТОМОРФИЗМЫ СЕТЕЙ ПЕТРИ
Ю.А. Белов

Ярославский государственный университет им. П.Г. Демидова, факультет информатики и вычислительной техники, каф. теоретической информатики,
Россия, 150000, Ярославль, belov45@yandex.ru

1.Определения.
Обыкновенная сеть Петри -- это двудольный ориентированный граф со взвешенными дугами. Вершины первой доли образуют конечное множество Р и называются позициями, вершины второй доли образуют множество переходов Т. Множество дуг есть F (Р Т) (Т Р), w: (Р Т) (Т Р) N={0, 1, 2, …n,…} неотрицательная целочисленная весовая функция. Полагаем, что если (p, t) (или (t, p)) не дуга, то w(p, t)=0 (или w(t, p)=0), если дуга, то w(p, t)>0. Множество S всех возможных состояний сети определяется как S=Nk, где k=|P| -- называется размерностью сети.
Пусть имеются две сети: D(P1, T1, L) и H(P2, T2, L) с одинаковым множеством меток (действий).
Говорят, что имеется изоморфное отображение сети D на H, если существует биекция : S1 S2 состояний одной системы на состояния другой такая, что s, s' S1 s s' тогда и только тогда, когда (s) (s'). Здесь над переходами указаны метки, чтобы подчеркнуть, что соответствующие переходы в D и H задают одинаковые действия.
Изоморфизм означает, что для внешнего наблюдателя сети функционируют идентично. Отметим также, что каждый изоморфизм определяет отношение бисимулярности для сетей D и H – основное отношение взаимного моделирования, изучаемое для сетей Петри [1, 3].
Если изоморфизм кроме того, сохраняет порядок, то есть x y в S1 тогда и только тогда, когда (x) (y) в S2, он называется монотонным.
Изоморфное отображение сети на себя называется автоморфизмом.
Группа Autm(D) монотонных автоморфизмов произвольной сети Петри D конечна и определяется некоторой группой подстановок на множестве Р позиций сети [7].
Теорема 2.
Для всякой конечной группы Г существует такая сеть Петри D, что Г изоморфно вкладывается в группу монотонных автоморфизмов сети Autm(D) [6, 7].
Теорема 3.
Для всякой счётной группы Г существует такая сеть Петри D, что Г изоморфно вкладывается в группу всех автоморфизмов сети Aut(D).
Первые примеры сетей с бесконечными группами автоморфизмов, отмеченные в теореме 3, имели некоторое свойство вырожденности, когда срабатывание перехода не меняет состояния сети. Теперь удалось построить более содержательные примеры невырожденных сетей, что интересно в связи с проблемой бисимуляции (взаимного моделирования) двух состояний сети.
Просмотров: 1473 / Добавлено: belov / Дата: 2017-11-23
Comments 1
Всего комментариев: 0
Только зарегистрированные пользователи могут оставлять комментарии.
[ Registration | Login ]