This article is cited in 1 scientific paper (total in 1 paper)
Homomorphisms of shift registers into linear automata
V. I. Solodovnikov
The paper is devoted to describing all homomorphisms of shift registers over finite fields with feedback function which is a permutation function with respect to the input variable into linear automata. We prove that the linear automaton which is the homomorphic image of a shift register is always isomorphic to a linear shift register. Therefore, according to the theorem proved by the author earlier, the question on the homomorphisms of linear shift registers into linear automata reduces to the question on the decomposition of a function (or the polynomial representing the function) into the so-called shift-composition of two functions (polynomials), where the left function is an affine function. We also prove that any polynomial is uniquely representable in the form of a sum of shift-compositions of linear polynomials and monomials with the first variable. These linear polynomials are in correspondence with polynomials of one variable and the question on the decomposition is reduced to the search for the common divisors of these polynomials of one variable. We give some simple conditions sufficient for absence of nontrivial inner homomorphisms of shift registers into linear automata.
PDF file (145 kB)
Discrete Mathematics and Applications, 2008, 18:4, 413–425
V. I. Solodovnikov, “Homomorphisms of shift registers into linear automata”, Diskr. Mat., 20:4 (2008), 89–101; Discrete Math. Appl., 18:4 (2008), 413–425
Citation in format AMSBIB
\paper Homomorphisms of shift registers into linear automata
\jour Diskr. Mat.
\jour Discrete Math. Appl.
Citing articles on Google Scholar:
Related articles on Google Scholar:
Cycle of papers
This publication is cited in the following articles:
I. V. Cherednik, “Lineinoe razlozhenie diskretnykh funktsii v terminakh operatsii sdvig-kompozitsii”, PDM. Prilozhenie, 2019, no. 12, 68–73
|Number of views:|