ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ПОСТРОЕНИЯ ТЕРМОВ
МИНИМАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

Дадеркин, Д.О.

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ПОСТРОЕНИЯ ТЕРМОВ МИНИМАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

Дата публикации: 2016

Дата публикации в реестре: 2020-03-18T12:53:36Z

Аннотация:

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

Ключевые слова:
510.6 Математическая логика

Тип: Статья