The Algorithm for Checking Transitivity of Mappings Associated with the Finite State Machines from the Groups ASp
The paper deals with a question of determining the property of transitivity for mappings deﬁned by ﬁnite automata. A criterion of transitivity for mappings deﬁned by ﬁnite automata on the words of ﬁnite length in terms of ﬁnite automata and trees of deterministic functions is presented. It is shown that for ﬁnite 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. Based on these results a matrix algorithm is constructed for checking transitivity of mappings associated with initial automata from groups ASp. 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.