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