Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


For citation:

Karandashov M. V. The Algorithm for Checking Transitivity of Mappings Associated with the Finite State Machines from the Groups ASp. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2017, vol. 17, iss. 1, pp. 85-95. DOI: 10.18500/1816-9791-2017-17-1-85-95, EDN: YNBYCZ

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
22.02.2017
Full text:
(downloads: 179)
Language: 
Russian
Heading: 
UDC: 
519.7
EDN: 
YNBYCZ

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

Autors: 
Karandashov Maksim Valer'evich, Saratov State University
Abstract: 

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. 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.

References: 
  1. Grigorchuk R. I., Nekrashevych V. V., Sushchanskii V. I. Automata, Dynamical Systems and Groups. Proc. Steklov Inst. Math., 2000, vol. 231, pp. 128–203 (in Russian).
  2. Tyapaev L. B. Tranzitivnye semejstva avtomatnykh otobrazhenij [Transitive family automaton mappings]. Komp’iuternye nauki i informatsionnye tekhnologii : materialy Mezhdunar. nauch. konf. [Computer Science and Information Technologies : Proc. Intern. Sci. Conf.]. Saratov, Publ. center “Nauka”, 2014, pp. 244–247 (in Russian).
  3. Tyapaev L. B. Transitive families and measure-preservind an N-unit delay mappings. Komp’iuternye nauki i informatsionnye tekhnologii : materialy Mezhdunar. nauch. konf. [Computer Science and Information Technologies : Proc. Intern. Sci. Conf.]. Saratov, Publ. Center “Nauka”, 2016, pp. 425–429. (in Russian).
  4. Gill A. Introduction to the theory of finite-state machines. New York, Toronto, Ontario, London, McGraw-Hill Book Co., Inc., 1962. 207 p. (Russ. ed. : Gill A. Vvedenie v teoriiu konechnykh avtomatov. Moscow, Nauka, 1966. 272 p.)
  5. Karandashov M. V. Issledovanie biektivnykh avtomatnykh otobrazhenii na kol’tse vychetov po moduliu 2 k [Research bijective automaton mappings on the ring of residues modulo 2 k ]. Komp’iuternye nauki i informatsionnye tekhnologii : materialy Mezhdunar. nauch. konf. [Computer Science and Information Technologies : Proc. Intern. Sci. Conf.]. Saratov, Publ. Center “Nauka”, 2014, pp. 148–152 (in Russian). 
  6. Yablonsky S. V. Vvedenie v diskretnuiu matematiku : Ucheb. posobie dlia vuzov [Introduction to Discrete Mathematics : Textbook. manual for schools]. Moscow, Nauka, 1986. 384 p. (in Russian).
  7. Kaluzhin L. A., Sushchanskii V. I. Preobrazovaniia i perestanovki: Per. s ukr. [Transformations and permutations : Trans. RBM]. Moscow, Nauka, 1985. 160 p. (in Russian).
  8. Aleshin S. V. Finite automata and Burnside’s problem for periodic groups. Math. Notes, 1972, vol. 11, iss. 3, pp. 199–203. DOI: https://doi.org/10.1007/BF01098526.
Received: 
18.09.2016
Accepted: 
29.01.2017
Published: 
28.02.2017