?
О полиномиальной разрешимости проблемы эквивалентности программ в перегородчатых моделях над прогрессивными полугруппами
Проблема эквивалентности программ формулируется так: выяснить, имеют ли две программы схожие (эквивалентные) поведения. Известен алгоритм полиномиального сведения проблемы эквивалентности в перегородчатых моделях программ с процедурами к двум проблемам в моделях программ без процедур с той же семантикой программных операторов: эквивалентности и совместного останова. Проблема совместного останова формулируется так: выяснить, существует ли общий контекст работы программ, при котором обе программы успешно завершают выполнение. Эта проблема, насколько нам известно, ранее никем не исследовалась для нетривиальных моделей программ (отличных от конечных автоматов). Нами предлагается метод решения этой проблемы, позволяющий с учётом известных результатов получить описание полиномиальных алгоритмов решения проблемы эквивалентности для широкого класса перегородчатых моделей программ.