Geodesic
The algorithm for checking transitivity of mappings associated with the finite state machines from the groups $AS_p$
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 17 (2017) no. 1, pp. 85-95 
M. V. Karandashov. The algorithm for checking transitivity of mappings associated with the finite state machines from the groups $AS_p$. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 17 (2017) no. 1, pp. 85-95. http://geodesic.mathdoc.fr/item/ISU_2017_17_1_a7/
@article{ISU_2017_17_1_a7,
     author = {M. V. Karandashov},
     title = {The algorithm for checking transitivity of mappings associated with the finite state machines from the groups~$AS_p$},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {85--95},
     year = {2017},
     volume = {17},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2017_17_1_a7/}
}
TY  - JOUR
AU  - M. V. Karandashov
TI  - The algorithm for checking transitivity of mappings associated with the finite state machines from the groups $AS_p$
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2017
SP  - 85
EP  - 95
VL  - 17
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/ISU_2017_17_1_a7/
LA  - ru
ID  - ISU_2017_17_1_a7
ER  - 
%0 Journal Article
%A M. V. Karandashov
%T The algorithm for checking transitivity of mappings associated with the finite state machines from the groups $AS_p$
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2017
%P 85-95
%V 17
%N 1
%U http://geodesic.mathdoc.fr/item/ISU_2017_17_1_a7/
%G ru
%F ISU_2017_17_1_a7

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

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 $AS_p$ an algorithm can be constructed for checking transitivity. To prove this fact some properties of Abelian groups of permutations are used. Based on these results a matrix algorithm is constructed for checking transitivity of mappings associated with initial automata from groups $AS_p$. The special feature of this algorithm is its independence from lengths of the considered words. Results of numerical experiments and the upper bound of complexity of the algorithm are presented.

[1] Grigorchuk R. I., Nekrashevych V. V., Sushchanskii V. I., “Automata, Dynamical Systems and Groups”, Proc. Steklov Inst. Math., 231, 2000, 134–214 (in Russian) | Zbl

[2] Tyapaev L. B., “Transitive family automaton mappings”, Computer Science and Information Technologies, Proc. Intern. Sci. Conf., Publ. center “Nauka”, Saratov, 2015, 244–247 (in Russian)

[3] Tyapaev L. B., “Transitive families and measure-preservind an N-unit delay mappings”, Computer Science and Information Technologies, Proc. Intern. Sci. Conf., Publ. Center “Nauka”, Saratov, 2016, 425–429 (in Russian)

[4] Gill A., Introduction to the theory of finite-state machines, McGraw-Hill Book Co., Inc., New York–Toronto–Ontario–London, 1962, 207 pp. | MR | MR

[5] Karandashov M. V., “Research bijective automaton mappings on the ring of residues modulo $2^k$”, Computer Science and Information Technologies, Proc. Intern. Sci. Conf., Publ. Center “Nauka”, Saratov, 2014, 148–152 (in Russian)

[6] Yablonsky S. V., Introduction to Discrete Mathematics, Textbook. manual for schools, Nauka, M., 1986, 384 pp. (in Russian) | MR

[7] Kaluzhin L. A., Sushchanskii V. I., Transformations and permutations, Trans. RBM, Nauka, M., 1985, 160 pp. (in Russian)

[8] Aleshin S. V., “Finite automata and Burnside's problem for periodic groups”, Math. Notes, 11:3 (1972), 199–203 | DOI | MR | Zbl | Zbl