О проблеме эквивалентности последовательных программ с процедурами

Стажер-исследователь Казбекова Диана выступила на семинаре лаборатории

22 сентября прошел онлайн-семинар лаборатории процессно-ориентированных информационных систем факультета компьютерных наук.

Диана Казбекова, студентка 2 года магистерской программы "Системная и программная инженерия", представила свою исследовательскую работу о проблеме эквивалентности последовательных программ с процедурами под руководством ведущего научного сотрудника лаборатории Владимира Анатольевича Захарова.

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

 

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

 

С презентацией можно ознакомиться по ссылке О проблеме эквивалентности