Распознавание рекуррентных последовательностей, порождаемых консервативными функциями | Прикладная дискретная математика. 2014. № 7 (Приложение).

Пусть K - класс функций вида f : R ^ R, где n = 1,2,3,..., и S (K,N) - множество начальных отрезков длины N рекуррентных последовательностей, построенных при помощи функций из K. Рассматривается задача распознавания свойства «х е S (K, N)» для произвольной последовательности x е R . В случае, когда K - класс консервативных функций над кольцом R = Z _pn, предлагается алгоритм решения этой задачи, битовая сложность которого O (N log N).