Группы гомологий асинхронных систем переходов. Практическое решение задач

УДК 681.3.06.

(Husainov Ahmet Aksanovitsh)

Комсомольский-на-Амуре государственный технический университет, Ткаченко Владимир Викторович

(Tkatshenko Vladimir Viktorovitsh)

Комсомольский-на-Амуре государственный педагогический университет.

Группы гомологий асинхронных систем переходов

(Homology groups of asynchronous transition systems).

Введено определение групп гомологий асинхронной системы переходов. Вычислены группы гомологий произведения асинхронных систем переходов

(It is introduced the definition of homology groups of asynchronous transition systems. It is computed the homology groups of  the product of asynchronous transition systems.)

1. Категория асинхронных систем переходов.

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

Асинхронной системой переходов [1], называется пятерка , состоящая из произвольных множеств  и , элемента , подмножества  и бинарного, антирефлексивного, симметричного отношения , удовлетворяющих условиям:

(1)

(2)

(3)  

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

Пример 1.1. Рассмотрим множество состояний  некоторого массива  чисел целого типа и операции  и , при , где

 действует как , а   как  . Начальное состояние  определим как , и  при . Получим асинхронную систему переходов , в которой  будет состоять из троек  и , определенных в случаях, когда  получено из  с помощью операции  (или ). Если  то пары операций  будут независимыми, такие пары можно отнести к .

Асинхронные системы тесно связаны с сетями Петри. Каждой сети Петри в работе [1] ставится в соответствие некоторая асинхронная система. Это соответствие продолжается до функтора.

Аксиома (2) асинхронной системы переходов означает, что для каждого  множество троек  составляет частичную функцию, область определения которой содержится в  и, в силу (1), не пуста.

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

Рассмотрим категорию, объектами которой служат асинхронные системы переходов [1]. Морфизмы между асинхронными системами переходов  определяются как пары , состоящие из функций  и пунктированных отображений , таких, что  и

 .

Наше наблюдение состоит в том, что существует функтор из категории асинхронных систем переходов в категорию пунктированных множеств, на которых действуют моноиды.

Пунктированным (правым) полигоном называется тройка , состоящая из моноида , действующего справа на пунктированном множестве . Действие определяется как функция  , удовлетворяющая условиям:

1),

2).

Здесь 1 – нейтральный элемент моноида .

Если рассматривать моноид  как категорию с одним объектом , то пунктированный полигон будет определять функтор, для которого на единственном объекте и

Определим морфизмы полигонов  как пары , состоящие из гомоморфизма моноидов  и естественного отображения , удовлетворяющих при всех  .

Если рассматривать моноид как категорию с единственным объектом, то морфизму полигонов будет соответствовать естественное преобразование функторов , которое на единственном объекте будет равно отображению .

Композиция морфизмов    полигонов определяется как пара, состоящая из гомоморфизма  и отображения . Тождественный морфизм равен , где - тождественный гомоморфизм, а -тождественное отображение. Обозначим  через , опуская символ действия.

Каждой асинхронной системе переходов  поставим в соответствие пунктированный полигон , где  - моноид с множеством образующих  удовлетворяющих соотношениям  для всех . Действие моноида  определено действием элементов  на множестве , как , если , и , если не существует элементов , для которых . Положим .