RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2011 Volume 2, Issue 1, Pages 97–117 (Mi mvk27)

This article is cited in 1 paper

Layers of a finite automaton

V. G. Smirnov

Academy of Cryptography of Russian Federation, Moscow

Abstract: 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.

Key words: finite automata, semigroups of transforms, transition graph.

UDC: 519.16

Received 22.IV.2010

DOI: 10.4213/mvk27



© Steklov Math. Inst. of RAS, 2024