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.