RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskr. Mat., 2008, Volume 20, Issue 4, Pages 89–101 (Mi dm1029)  

This article is cited in 1 scientific paper (total in 1 paper)

Homomorphisms of shift registers into linear automata

V. I. Solodovnikov


Abstract: 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.

DOI: https://doi.org/10.4213/dm1029

Full text: PDF file (145 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2008, 18:4, 413–425

Bibliographic databases:

UDC: 519.7
Received: 24.12.2006

Citation: 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
\Bibitem{Sol08}
\by V.~I.~Solodovnikov
\paper Homomorphisms of shift registers into linear automata
\jour Diskr. Mat.
\yr 2008
\vol 20
\issue 4
\pages 89--101
\mathnet{http://mi.mathnet.ru/dm1029}
\crossref{https://doi.org/10.4213/dm1029}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2500607}
\zmath{https://zbmath.org/?q=an:05618991}
\elib{http://elibrary.ru/item.asp?id=20730269}
\transl
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 4
\pages 413--425
\crossref{https://doi.org/10.1515/DMA.2008.030}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-53349119039}


Linking options:
  • http://mi.mathnet.ru/eng/dm1029
  • https://doi.org/10.4213/dm1029
  • http://mi.mathnet.ru/eng/dm/v20/i4/p89

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Cycle of papers

    This publication is cited in the following articles:
    1. I. V. Cherednik, “Lineinoe razlozhenie diskretnykh funktsii v terminakh operatsii sdvig-kompozitsii”, PDM. Prilozhenie, 2019, no. 12, 68–73  mathnet  crossref
  • Дискретная математика
    Number of views:
    This page:370
    Full text:139
    References:39
    First page:19

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020