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

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