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

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