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

Авторы

Захаров В.А., Соколова К.А.

Аннотация

Исследована проблема эквивалентности в классе бесповторных металинейных унарных рекурсивных программ. Рекурсивные описания определяемых функций в таких программах удовлетворяют следующему требованию: для каждой определяемой функции существует пара термов из тела ее описания, которые оканчиваются различными базовыми операторами (функциями). Для указанного класса рекурсивных программ удалось построить полиномиальный по времени алгоритм, разрешающий эквивалентность программ.

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

рекурсивная программа, металинейная программа, эквивалентность, разрешающий алгоритм, сложность

Издание

Труды IV Международной конференции 'Дискретные модели в теории управляющих систем', 2000, МАКС-Пресс, с. 29-31.

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

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

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

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