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

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