Geodesic
Finite automata and numbers
Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 3-20.

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

We study finite automata representations of numerical rings. Such representations correspond to the class of linear $p$-adic automata that compute homogeneous linear functions with rational coefficients in the ring of $p$-adic integers. Finite automata act both as ring elements and as operations. We also study properties of transition diagrams of automata that compute a function $f(x)=cx$ of one variable. In particular we obtain precise values for the number of states of such automata and show that for $c>0$ transition diagrams are self-dual (this property generalises self-duality of Boolean functions). We also obtain the criterion for an automaton computing a function $f(x)=cx$ to be a permutation automaton, and fully describe groups that are transition semigroups of such automata.
Keywords: linear automata, $p$-adic numbers, automata structure, transition diagrams, transition semigroups. 
@article{DM_2015_27_4_a0,
     author = {S. V. Aleshin and P. A. Panteleev},
     title = {Finite automata and numbers},
     journal = {Diskretnaya Matematika},
     pages = {3--20},
     publisher = {mathdoc},
     volume = {27},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_4_a0/}
}
TY  - JOUR
AU  - S. V. Aleshin
AU  - P. A. Panteleev
TI  - Finite automata and numbers
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 3
EP  - 20
VL  - 27
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_4_a0/
LA  - ru
ID  - DM_2015_27_4_a0
ER  - 
%0 Journal Article
%A S. V. Aleshin
%A P. A. Panteleev
%T Finite automata and numbers
%J Diskretnaya Matematika
%D 2015
%P 3-20
%V 27
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2015_27_4_a0/
%G ru
%F DM_2015_27_4_a0
S. V. Aleshin; P. A. Panteleev. Finite automata and numbers. Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 3-20. http://geodesic.mathdoc.fr/item/DM_2015_27_4_a0/

[1] Lunts A. G., “$p$-adicheskii apparat v teorii konechnykh avtomatov”, Probl. kibernetiki, 14 (1965), 17–30

[2] Gill A., Lineinye posledovatelnye mashiny, Nauka, M., 1974, 287 pp. | MR

[3] Mandelbaum D., “A comparison of linear sequential circuits and arithmetic sequences”, IEEE Trans Electr. Comput., EC-16:2 (1967), 151–157 | DOI | MR | Zbl

[4] Klapper A., Goresky M., “$2$-adic shift registers”, Fast Software Encryption, Lect. Notes Comput. Sci, 809, Springer-Verlag, London, UK, 1994, 174–178 | DOI | Zbl

[5] Vuillemin J. E., “On circuits and numbers”, IEEE Trans. Computers, 43:8 (1994), 868–879 | DOI | MR | Zbl

[6] Hansen H. H., Costa D., Rutten J., “Synthesis of {M}ealy machines using derivatives”, Proc. CMCS 2006, Electr. Notes Theor. Comput. Sci., 164:1 (2006), 27–45 | DOI | MR | Zbl

[7] Brunner A. M., Sidki S., “The generation of ${GL}(n, \mathbb{Z})$ by finite state automata”, Int. J. Algebra and Computation, 8:1 (1998), 127–139 | DOI | MR | Zbl

[8] Lagorce N., “A convolutional-like approach to $p$-adic codes”, Discrete Applied Mathematics, 111:1-2 (2001), 139–155 | DOI | MR | Zbl

[9] Chasovskikh A. A., “O polnote v klasse konechnykh avtomatov, vychislyayuschikh nekotorye affinnye funktsii”, Intellektualnye sistemy, 17 (2013), 202–205

[10] Anashin V., Khrennikov A., Applied Algebraic Dynamics, W. de Gruyter Co, Berlin, 2009, 533 pp. | MR | Zbl

[11] Anashin V., “Automata finiteness criterion in terms of van der {P}ut series of automata functions”, $p$-Adic Numbers, Ultrametric Analysis and Applications, 4:2 (2012), 151–160 | DOI | MR | Zbl

[12] Krylov P. A., Mikhalev A. V., Tuganbaev A. A., Abelevy gruppy i ikh koltsa endomorfizmov, Faktorial Press, M., 2006, 512 pp.

[13] Kudpyavtsev V. B., Aleshin S. V., Podkolzin A. S., Elementy teorii avtomatov, Izd-vo MGU, M., 1978, 216 pp.

[14] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985, 320 pp. | MR

[15] Kargapolov M. I., Merzlyakov Yu. I., Osnovy teorii grupp, 3-e izd., Nauka, M., 1982, 288 pp. | MR

[16] Shumakova E. O., “Tsentralnye edinitsy tselochislennykh gruppovykh kolets metatsiklicheskikh grupp {F}robeniusa”, Sib. elektron. matem. izv., 5 (2008), 691–698 | MR | Zbl

[17] Prakhar K. P., Raspredelenie prostykh chisel, Mir, M., 1967, 513 pp. | MR