автоматные отображения

The Algorithm for Checking Transitivity of Mappings Associated with the Finite State Machines from the Groups ASp

Authors: Karandashov M. V.

The paper deals with a question of determining the property of transitivity for mappings defined by finite automata. A criterion of transitivity for mappings defined by finite automata on the words of finite length in terms of finite automata and trees of deterministic functions is presented. It is shown that for finite automata from groups ASp an algorithm can be constructed for checking transitivity. To prove this fact some properties of Abelian groups of permutations are used.

The Geometric Form of Automaton Mappings, Recurrent and Z-recurrent Definition of Sequences

Authors: Tverdokhlebov V. A.

For automaton mappings we present a method to construct geometric images, a method for complexity estimate by geometric forms, a method of Z-recurrent definition of sequences. A method for complexity estimate for finite sequences by recurrent and Z-recurrent numerical indicators is proposed. Numerical indicators of recurrent and Z-recurrent definitions of sequences are systematized into the spectrum of recurrent definitions with 5 levels of numerical indicators.