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/}
}
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/