Сборники трудов ИСП РАН


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

А. Э. Молчанов (МГУ, Москва)

Аннотация

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

Ключевые слова

алгебраические модели программ с процедурами; система эквивалентных преобразований; уравновешенная модель программ с левым сокращением

Издание

Труды Института системного программирования РАН, том 27, вып. 2, 2015, стр. 173-188.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(2)-11

Полный текст статьи в формате pdf Вернуться к содержанию тома