Разрешимость эквивалентности в перегородчатых моделях программ

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