Алгоритм распознавания полноты в функциональной системе $L(\mathbb Z)$

Предложен алгоритм, распознающий полноту (относительно суперпозиции) в функциональной системе полиномов первой степени над кольцом $\mathbb {Z}$. Оценены временная и емкостная сложности алгоритма. Алгоритм можно применять и для решения нескольких иных задач: распознавания свойств одного полинома и проверки полноты некоторых специальных систем. Работа выполнена при финансовой поддержке РФФИ (проекты 13–01–00684, 11–01–00792a).