Семинар лаборатории ПОИС: Быстрые алгоритмы проверки эквивалентности программ в моделях с полугрупповой семантикой

В докладе Владислава Подымова (ВМиК МГУ) были представлены результаты, полученные в рамках исследования проблемы эквивалентности в моделях последовательных и рекурсивных программ с семантикой, определяемой на основе полугрупп.

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