On primitivity of mixing digraphs for substitutions of shift registers

V. S. Grigoriev ; V. M. Fomichev

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 14-16

Résumé

Let $g$ and $h$ be substitutions defined by binary feedback left- and right-shift registers $R_l$ and $R_r$ respectively on their sets of states, $n$ be the length of each of these registers, $f_l=x_1\oplus\phi(x_2,\dots,x_n)$ and $f_r=x_n\oplus\psi(x_1,\dots,x_{n-1})$ be the feedback functions of $R_l$ and $R_r$ respectively, and $i_1,\dots,i_m$ be the numbers of the register stages which are the inputs of the feedback in $R_l$, $1=i_1$. So $x_{i_1},\dots,x_{i_m}$ are all essential variables of the function $f_l$. Let $G(s)$ be a mixing digraph for a substitution $s\in\{g,h,gh,hg\}$. We prove the following statements: 1) suppose, $g^{-1}=h$, then $G(g)$ is primitive iff $G(g^{-1})$ is primitive; in this case, $\exp G(g)=\exp G(g^{-1})$ if $i_k+i_{m+2-k}=n+2$ for all $k\in\{2,\dots,m\}$; 2) the set of arcs in $G(gh)$ consists of $n$ loops (one at each vertex) and arcs $(i,n)$, $i\in\{1,\dots,n-1\}$, such that $x_i$ is an essential variable of the function $\psi(x_1,\dots,x_{n-1})\oplus\phi(x_1,\dots,x_{n-1})$; 3) the set of arcs in $G(hg)$ consists of $n$ loops (one at each vertex) and arcs $(i,1)$, $i\in\{2,\dots,n\}$, such that $x_i$ is an essential variable of the function $\psi(x_2,\dots,x_n)\oplus\phi(x_2,\dots,x_n)$; 4) suppose, $h$ is a triangular substitution on $\{0,1\}^n$ and $G(g)$ is primitive; then the digraphs $G(g)\cdot G(h)$ and $G(h)\cdot G(g)$ are also primitive; in this case the exponent of each of these digraphs does not exceed $\exp G(g)$.

Détail

Keywords: mixing digraph, primitive digraph, exponent of graph, shift register
Mots-clés : triangle transformation.