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


Применение алгоритмов проверки эквивалентности для оптимизации программ

В.А.Захаров (ИСП РАН, Москва; МГУ, Москва; МФТИ, Москва; ВШЭ, Москва), В.В. Подымов (МГУ, Москва; ВШЭ, Москва)

Аннотация

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

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

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

Издание

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

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

DOI: 10.15514/ISPRAS-2015-27(4)-8

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