The recognition of recurrent sequences generated by conservative functions.pdf Задача распознавания последовательностей состоит в том, чтобы по заданной последовательности сказать, возможно ли её построить рекуррентно при помощи функции из определённого класса. Так, для распознавания свойства линейности над полем используется алгоритм Берлекэмпа - Месси [1, 2], обобщённый в работах В. Л. Куракина [3] для колец и модулей. В работах В. С. Анашина [4] предложено для построения рекуррентных последовательностей использовать полиномиальные, дифференцируемые и консервативные функции над кольцом. Такие функции имеют эффективную программную и аппаратную реализацию. В связи с этим в работе рассматриваются функции, сохраняющие систему эквивалентностей, частным случаем которых являются консервативные. Пусть П - конечное множество булевых функций, которое назовём базисом. Схема из функциональных элементов [5] - это ориентированный граф без циклов, где каждый вход помечен некоторой переменной, остальные вершины помечены базисными функциями. Если вершина помечена функцией от n аргументов, то её полустепень захода равна n. Сложностью схемы назовем число вершин в ней. Пусть R - конечное k-элементное множество; R* - множество всех бесконечных последовательностей с элементами из R; Pr - класс всех функций вида f : Rn ^ R при n = 1, 2, 3,... Определение 1. Последовательность x1x2x3 ... Е R* называется рекуррентной над классом K С PR, если для некоторого n существует функция f от n аргументов в классе K, такая, что f (xi,..., xn+i-1) = xn+i при всех i = 1, 2, 3,... Для любого целого положительного N обозначим через S (K, N) множество начальных отрезков длины N рекуррентных последовательностей над классом функций K. Далее рассматривается задача распознавания свойства «x Е S (K, N)» для x Е RN. Нас интересует сложность алгоритма, решающего данную задачу, как функция растущего N. Назовём S (K, N)-схемой схему из функциональных элементов, которая распознает названное выше свойство. При этом предполагается, что буквы алфавита R кодируются двоичными наборами фиксированной длины c и последовательности подаются на вход схемы в закодированном виде - наборами длины Nc. Перейдём к описанию класса K. Определение 2. Пусть е С R1 -отношение на множестве R, A С Rn. Частичная функция f : A ^ R сохраняет отношение е, если для любых наборов (x11,... ,x11), ... , (xn1,... ,xni), удовлетворяющих отношению е и таких, что функция f определена на наборах (xn,... ,xn1), ..., (x1i,... ,xni), набор (f (xn,... ,xn1), ..., f (x^,... ,xni)) также удовлетворяет е. Пусть е = {е1,...,ет} - система эквивалентностей на множестве R, такая, что е1 1Э е2 1Э ... D ет, и P_Rn) (е) - класс функций от n аргументов, сохраняющих все эквивалентности из е. Если R = Zpm и е - система сравнимостей по модулям p, p2, ... , pm-1, то P_Rn) (е) -это класс консервативных функций. Будем решать поставленную задачу для класса K = Р£°(е). Важной является следующая Лемма 1. Путь A С Rn. Частичная функция f : A ^ R, сохраняющая все эквивалентности из е, может быть продолжена до полностью определенной функции в классе pRn) (е). Лемма 1 позволяет построить последовательность S (K, N)-схем сложности O(N2). Теорема 1. Для любого n существует последовательность S (K, N)-схем сложности O (N log2 N.

Скачать электронную версию публикации