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

В статье предлагается подход к построению алгоритмов распознавания свойств $k$-значных функций, заданных полиномами (при простых $k$). Этот подход опирается на вводимое в статье понятие обобщенного полинома над системой функций. Доказывается критерий однозначности представимости $k$-значных функций обобщенными полиномами и основная теорема, с описанием условий, при которых можно построить полиномиальные распознающие алгоритмы. Приведены примеры применения основной теоремы для распознавания свойств сохранения предикатов $k$-значными функциями.
Работа поддержана Российским фондом фундаментальных исследований, грант 12–00706–а.