RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2023 Issue 16, Pages 141–143 (Mi pdma630)

This article is cited in 1 paper

Applied Theory of Coding and Automata

Periodic properties of a finite automaton generator

P. K. Obukhov, I. A. Pankratova

Tomsk State University

Abstract: The periodic properties of a two-stage finite automaton generator $G=A_1\cdot A_2$ are studied, where $A_1=(\mathbb{F}_2^n,\mathbb{F}_2, g_1, f_1)$ (it is autonomous), $g_1:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^n$, $f_1:\mathbb{F}_2^n\rightarrow\mathbb{F}_2$, $A_2 = (\mathbb{F}_2,\mathbb{F}_2^m,\mathbb{F}_2,g_2,f_2)$, $g_2:\mathbb{F}_2\times\mathbb{F}_2^m\rightarrow\mathbb{F}_2^m$, $f_2:\mathbb{F}_2\times\mathbb{F}_2^m\rightarrow\mathbb{F}_2$, $n,m\geq 1$. It is obtained that the maximum value of the generator period is $2^{n+m}$. Some necessary conditions for its achievement are formulated, namely: 1) the function $g_1$ is a full cycle substitution; 2) changing the initial state $x(1)$ or $y(1)$ does not affect the period of the generator; 3) function $f_1$ is not a constant; 4) at least one of the subfunctions $f_2(0,\cdot)$ and $f_2(1,\cdot)$ is not a constant; 5) the subfunctions $g_2(0,\cdot)$ and $g_2(1,\cdot)$ of the transition function $g_2$ are substitutions; 6) $y(2^ni+j)\neq y(2^nk+j)$ for all $i,k\in\{0,\ldots,2^m-1\}$, $i\neq k$, $j=1,\ldots,2^n$.

Keywords: finite automaton generator, substitutions, periodic sequences.

UDC: 519.7

DOI: 10.17223/2226308X/16/37



© Steklov Math. Inst. of RAS, 2024