Geodesic
On mixing digraphs of nonlinear substitutions for binary shift registers
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 6-9.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we research the class $R(n,m)$ of substitutions on $n$-dimensional vector space produced by the binary left-shift registers of the length $n$ with one feedback $f(x_1,\dots,x_n)=x_1\oplus\psi(x_2,\dots,x_n)$ essentially depending on $m$ variables, $3\le m\le n$. We have obtained the following double-ended estimate for the exponent of the mixing digraphs $\Gamma(g)$ for nonlinear substitutions $g\in R(n,m)$: $$ n+\left\lceil\frac{n-1}{m-1}\right\rceil-1\le\exp{\Gamma(g)}\le\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1, $$ where $D(g)=\{i_1,\dots,i_m\}$ is the set of indexes of essential variables of the shift register feedback function $f$, $1=i_1\dots$, $m\le n$; $\Delta(D)=\max\{i_2-i_1,\dots,i_m-i_{m-1},n-i_m\}$. We have also obtained some upper-bound estimates for the sum and for the ratio of exponents of mixing digraphs of substitution $g\in R(n,m)$ and its inverse substitution $g^{-1}$: \begin{gather*} \exp{\Gamma(g)}+\exp{\Gamma(g^{-1})}\le2\left(\Delta(D)+\left\lfloor\frac{n^2}m\right\rfloor\right)+i_m,\\ \frac{\exp{\Gamma(g)}}{\exp{\Gamma(g^{-1})}}\le\frac{\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1}{n+\left\lceil\frac{n-1}{m-1}\right\rceil-1}. \end{gather*}
Keywords: mixing digraph approach, primitive digraph, exponent of graph, shift register, Frobenius number. 
@article{PDMA_2018_11_a0,
     author = {V. S. Grigoriev},
     title = {On mixing digraphs  of nonlinear substitutions for binary shift registers},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {6--9},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a0/}
}
TY  - JOUR
AU  - V. S. Grigoriev
TI  - On mixing digraphs  of nonlinear substitutions for binary shift registers
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 6
EP  - 9
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a0/
LA  - ru
ID  - PDMA_2018_11_a0
ER  - 
%0 Journal Article
%A V. S. Grigoriev
%T On mixing digraphs  of nonlinear substitutions for binary shift registers
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 6-9
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a0/
%G ru
%F PDMA_2018_11_a0
V. S. Grigoriev. On mixing digraphs  of nonlinear substitutions for binary shift registers. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 6-9. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a0/

[1] Kogos K. G., Fomichev V. M., “Polozhitelnye svoistva neotritsatelnykh matrits”, Prikladnaya diskretnaya matematika, 2012, no. 4(18), 5–13

[2] Grigorev V. S., Fomichev V. M., “O primitivnosti peremeshivayuschikh podstanovok registrov sdviga”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 14–16

[3] Fomichev V. M., “Otsenki eksponentov primitivnykh grafov”, Prikladnaya diskretnaya matematika, 2011, no. 2(12), 101–112

[4] Fomichev V. M., “Novaya universalnaya otsenka eksponentov grafov”, Prikladnaya diskretnaya matematika, 2016, no. 3(33), 78–84

[5] Dulmage A. L., Mendelsohn N. S., “Gaps in the exponent set of primitive matrices”, Illinois J. Math., 8:4 (1964), 642–656 | MR | Zbl

[6] Fomichev V. M., Kyazhin S. N., “Lokalnaya primitivnost matrits i orgrafov”, Diskretnyi analiz i issledovanie operatsii, 24:1 (2017), 97–119 | DOI | MR | Zbl

[7] Lewin M., “A bound for a solution of a linear Diophantine problem”, J. London Math. Soc., 6 (1972), 61–69 | DOI | MR | Zbl

[8] Alfonsin R. J., The Diophantine Frobenius Problem, Oxford University Press, 2005, 260 pp. | MR | Zbl

[9] Sachkov V. N., Tarakanov V. E., Kombinatorika neotritsatelnykh matrits, TVP, M., 2000 | MR