Об эквивалентности металинейных унарных рекурсивных программ.

Авторы

Захаров В.А., Подымов В.В.

Аннотация

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

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

рекурсивная схема программ, металинейная программа, проблема эквивалентности

Издание

Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.), 2012, Изд-во механико-математического ф-та МГУ Москва, с. 157-159.

Научная группа

Теоретическая информатика

Все публикации за 2012 год

Все публикации