Сравнение причинной зависимости и семантики истинного параллелизма в контексте временных моделей

Сравнение причинной зависимости и семантики истинного параллелизма в контексте временных моделей

Язык статьи
Английский
Аннотация
Цель данной работы – установить взаимосвязи между различными параллельными моделями реального времени. Для достижения данной цели мы определили категорию временных причинных деревьев и исследовали, какое место занимает эта категория среди других категорий временных моделей. В частности, мы установили существование сопряженных функторов между категорией временных причинных деревьев и категорией временных структур событий, используя для этого более выразительную модель временных деревьев событий. Тем самым мы показали, что временные причинные деревья проще временных структур событий в том, что они отражают только один аспект семантики истинного параллелизма, а именно причинную зависимость, и не используют понятие события для задания отношения причинной зависимости. С другой стороны, модель временных причинных деревьев более выразительна, чем модель временных структур событий по следующей причине: для нее множество всех возможных последовательностей выполнения может быть определено в терминах дерева без каких-либо ограничений, а множество всевозможных последовательностей выполнения для временной структуры событий должно быть замкнутыми относительно операции перестановки параллельных переходов.
УДК
Страницы
71-100
Файл
gribovskaya.pdf218.95 КБ
Номер