Алгебра диоидов, Информация о событиях - Разработка программы для реализации редактора временных графов синхронизации

Множество D с двумя заданными на нем операциями (плюс) и (умножение) называется диоидом, если выполнены следующие аксиомы:

    § Ассоциативность. § Коммутативность сложения. § Левая дистрибутивность (умножение не обязано быть коммутативным). § Только левая, поскольку умножение не обязано быть коммутативным. § Существование нулевого элемента и единицы ( и соответственно). § Поглощающий нуль.

§ Идемпотентность сложения ().

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

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

Таким образом, множество всех степенных рядов вида:

Где, является диоидом. Существует отображение.

Замыкание Клини ("звездочка") определяется как бесконечная сумма:

Где:

.

Для уравнения верно, что:

    § Частным решением является ; § Если является решением, то ;
Информация о событиях

Когда мы говорим о типе события, для временных графов синхронизации подразумеваются события срабатывания переходов и тип ассоциируется с именем сработавшего перехода. Для перехода мы рассматриваем "фрагменты информации" о событиях как целочисленные пары. Во временном графе синхронизации фрагменты информации переносятся от входящих переходов к исходящим, на каждом переходе происходит объединение фрагментов информации. Принцип объединения продемонстрирован на рис. 4 и 6, до срабатывания перехода и после, соответственно.

Рисунок 4

объединение информации

Рисунок 5. Объединение информации

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

Возвращаясь к алгебре диоидов, определим операции и :

(1)

Таким образом, объединение информации теперь можно выполнять при помощи методов линейной алгебры на множестве диоидов. При использовании умножения, и задают сдвиг, например сдвиг по времени: сдвинет информацию, доступную при срабатывании перехода, на 6 временных тиков. Знак умножения, как и в обычной алгебре, можно опустить.

Пары чисел, при условии, что все события пронумерованы целыми числами, интерпретируются как "событие с номером случилось не раньше времени " или "на момент времени, номер последнего случившегося события не больше ".

При объединении информации некоторые фрагменты могут быть полностью доминировать над другими. Для наглядности представим юго-восточные конусы на декартовой плоскости на рис. 6. представьте точку, тогда по формуле (1):

Возвращаясь к определению множества, которое представляет все возможные ряды, в том числе с избыточной информацией. Поэтому авторы теории фильтруют при помощи отношения эквивалентности так, чтобы в итоговом фактормножестве остались лишь неубывающие ряды без избыточной информации (рис. 8). Обозначается как -- читается min max gd.

конусы и на плоскости раздельно

Рисунок 6. Конусы и на плоскости раздельно

доминирование после объединения

Рисунок 7. Доминирование после объединения

объединение без доминирования

Рисунок 8. Объединение без доминирования

Похожие статьи




Алгебра диоидов, Информация о событиях - Разработка программы для реализации редактора временных графов синхронизации

Предыдущая | Следующая