Теоретико-категорная характеризация семантик систем переходов первичных структур событий с отменяемыми событиями при сохранении причинной зависимости

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