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


Конечные автоматы в теории алгебраических схем программ

Р.И. Подловченко (МГУ, Москва)

Аннотация

Рассматриваемые в статье алгебраические модели программ обобщают две модели программ, введённые А.А. Ляпуновым и А.А. Летичевским. Показано, что алгебраические модели программ аппроксимируют компьютерные программы, через промежуточную формализацию. Центральное место в теории таких моделей занимает проблема эквивалентности схем программ. Существует достаточно много классов моделей, для которых эта проблема разрешима. Большинство разрешающих алгоритмов следуют структуре алгоритма проверки эквивалентности конечных автоматов. Целью данной статьи является выявляение этой связи. Вводится эквивалентное представление моделей программ, называемое матричными схемами. Такое представление структурно ближе к конечным автоматам, и показано, что проблема эквивалентности в подклассе матричных схем программ сводится к таковой для конечных автоматов. Рассматривается алгоритм, решающий проблему эквивалентности КА; он формулируется в терминах требований к конечным участкам путей выполнения автоматов. В результате удаётся сформулировать более общий метод, применимый к другим моделям. Приводятся необходимые требования, предъявляемые к моделям для применимости к ним указанного метода. Приводятся две модели, уравновешенная полугрупповая модель с левым сокращением и коммутативная модель с монотонными операторами, в который разрешимость проблемы эквивалентности установлена указанным методом.

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

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

Издание

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

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

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

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