• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Мероприятия

[ONLINE] Семинар НУЛ ПОИС: "О проблеме эквивалентности последовательных программ с процедурами"

Мероприятие завершено

22 сентября в 18:10 пройдет семинар научно-учебной лаборатории процессно-ориентированных информационных систем.

 

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

 

Докладчик – Казбекова Диана, стажер-исследователь НУЛ ПОИС.

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

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