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. 
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/
@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},
     year = {2018},
     number = {11},
     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
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
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a0/
%G ru
%F 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