Geodesic
Layers of a finite automaton
Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 1, pp. 97-117 
V. G. Smirnov. Layers of a finite automaton. Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 1, pp. 97-117. http://geodesic.mathdoc.fr/item/MVK_2011_2_1_a3/
@article{MVK_2011_2_1_a3,
     author = {V. G. Smirnov},
     title = {Layers of a~finite automaton},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {97--117},
     year = {2011},
     volume = {2},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2011_2_1_a3/}
}
TY  - JOUR
AU  - V. G. Smirnov
TI  - Layers of a finite automaton
JO  - Matematičeskie voprosy kriptografii
PY  - 2011
SP  - 97
EP  - 117
VL  - 2
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2011_2_1_a3/
LA  - ru
ID  - MVK_2011_2_1_a3
ER  - 
%0 Journal Article
%A V. G. Smirnov
%T Layers of a finite automaton
%J Matematičeskie voprosy kriptografii
%D 2011
%P 97-117
%V 2
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2011_2_1_a3/
%G ru
%F MVK_2011_2_1_a3

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

Layers of automaton are defined, their properties are investigated and conditions for a state of automata to belong to a layer are found. A notion of $t$-unrollment of initial automaton graph is introduced as an oriented graph with marked edges; this notion is used for reduction the enumeration of preimages of the output sequence segment to the construction of graph of solutions for a system of $k$-valued logic equations. An algorithm for the construction of such graph with complexity proportional to the number of vertices of $t$-unrollment is designed. The complexity may depend on $t$ polynomially or exponentially.

[1] Glukhov M. M., “O chislovykh parametrakh, svyazannykh s zadaniem konechnykh grupp sistemami obrazuyuschikh elementov”, Trudy po diskretnoi matematike, 1, TVP, M., 1997, 43–66 | MR | Zbl

[2] Lalleman Zh., Polugruppy i kombinatornye prilozheniya, Mir, M., 1985 | MR

[3] Lyapin E. S., Polugruppy, FIZMATLIT, M., 1960 | MR | Zbl

[4] Klifford A., Preston G., Algebraicheskaya teoriya polugrupp, v. 1, Mir, M., 1972 | Zbl

[5] Ore O., Teoriya grafov, Nauka, M., 1968 | MR

[6] Smirnov V. G., “Metody postroeniya grafov reshenii dlya sistem $k$-znachnykh uravnenii”, Trudy po diskretnoi matematike, 8, FIZMATLIT, M., 2004, 253–280

[7] Smirnov V. G., “Metody resheniya sistem diskretnykh uravnenii, osnovannye na postroenii grafa reshenii”, Trudy po diskretnoi matematike, 9, Gelios ARV, M., 2006, 308–339

[8] Smirnov V. G., “Metody resheniya sistem kvazisimmetricheskikh uravnenii i ikh primenenie k analizu generatorov s upravlyaemym dvizheniem”, Matematicheskie voprosy kriptografii, 1:3 (2010), 67–91

[9] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986

[10] Sumarokov S. N., “Zaprety dvoichnykh funktsii i obratimost dlya odnogo klassa shifruyuschikh ustroistv”, Obozr. prikl. i promyshl. matem., 1:1 (1994), 33–55 | Zbl