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

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. 
@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},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {2017},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2017_17_1_a7/
%G ru
%F ISU_2017_17_1_a7
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/