Geodesic
About transitive property of mappings associated with a~finite state machines from the groups~$AS_p$
Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 115-118.

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

Checking the transitive property of the automaton mappings is discussed. A general criterion for transitivity of automaton mappings on words of length $k\in\mathbb N$ is presented. For automata from groups $AS_p$, an algorithm for checking transitive property is proposed. The complexity of the algorithm depends on the number of automaton states and does not depend on the input word length. The upper bound of the algorithm complexity is specified.
Keywords: finite state machines, automata mappings, $AS_p$ groups, transitivity. 
@article{PDMA_2016_9_a45,
     author = {M. V. Karandashov},
     title = {About transitive property of mappings associated with a~finite state machines from the groups~$AS_p$},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {115--118},
     publisher = {mathdoc},
     number = {9},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2016_9_a45/}
}
TY  - JOUR
AU  - M. V. Karandashov
TI  - About transitive property of mappings associated with a~finite state machines from the groups~$AS_p$
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2016
SP  - 115
EP  - 118
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2016_9_a45/
LA  - ru
ID  - PDMA_2016_9_a45
ER  - 
%0 Journal Article
%A M. V. Karandashov
%T About transitive property of mappings associated with a~finite state machines from the groups~$AS_p$
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2016
%P 115-118
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2016_9_a45/
%G ru
%F PDMA_2016_9_a45
M. V. Karandashov. About transitive property of mappings associated with a~finite state machines from the groups~$AS_p$. Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 115-118. http://geodesic.mathdoc.fr/item/PDMA_2016_9_a45/

[1] Tyapaev L. B., “Tranzitivnye semeistva avtomatnykh otobrazhenii”, Diskretnye modeli v teorii upravlyayuschikh sistem, IX Mezhdunar. konf. (Moskva i Podmoskove, 20–22 maya 2015), Trudy, eds. V. B. Alekseev, D. S. Romanov, B. R. Danilov, MAKS Press, M., 2015, 244–247

[2] Gill A., Vvedenie v teoriyu konechnykh avtomatov, Nauka, M., 1966, 272 pp. | MR

[3] Karandashov M. V., “Issledovanie biektivnykh avtomatnykh otobrazhenii na koltse vychetov po modulyu $2^k$”, Kompyuternye nauki i informatsionnye tekhnologii, Materialy Mezhdunar. nauch. konf., Izdat. tsentr “Nauka”, Saratov, 2014, 148–152

[4] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Ucheb. posobie dlya vuzov, 2-e izd., pererab. i dop., Nauka, M., 1986, 384 pp. | MR

[5] Kaluzhnin L. A., Suschanskii V. I., Preobrazovaniya i perestanovki, Per. s ukr., 2-e izd., pererab. i dop., Nauka, M., 1985, 160 pp. | MR

[6] Aleshin S. V., “Konechnye avtomaty i problema Bernsaida o periodicheskikh gruppakh”, Matem. zametki, 11:3 (1972), 319–328 | MR | Zbl