Let K be a class of functions f : R
^ R, where n = 1, 2,... Suppose that S (K, N) is the set of all N-prefixes of recurrent sequences generated by functions from K. The recognition problem for the property "x G S(K, N)", where x G R
and K is the class of conservative functions over the ring R = Z
pm , is considered. For solving this problem, an algorithm of complexity O(N log
N) is offered.
Download file
Counter downloads: 225
- Title The recognition of recurrent sequences generated by conservative functions
- Headline The recognition of recurrent sequences generated by conservative functions
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 7 (Приложение)
- Date:
- DOI
Keywords
circuit of functional elements, recurrent sequences, conservative function, консервативные функции, рекуррентные последовательности, функциональные элементы, схемаAuthors
References
Wegener I. The Complexity of Boolean Functions. John Wiley & Sons Ltd, 1987.
Анашин В. С. Равномерно распределенные последовательности целых p-адических чисел // Математические заметки. 1994. Т. 55. №2. C.3-46.
Куракин В. Л. Алгоритм Берлекэмпа - Мэсси над конечными коммутативными кольцами // Проблемы передачи информ. 1999. №35. C. 38-50.
Massey J. L. Shift-register synthesis and BCH decoding // IEEE Trans. Inform. Theory. 1969. V. 15. No 1. Part 1. P. 122-127.
Berlekamp E. R. Algebraic Coding Theory. New York: Mc Craw-Hill, 1968. (Пер.: Берле-кэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.)
The recognition of recurrent sequences generated by conservative functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 7 (Приложение).
Download full-text version
Counter downloads: 1916