|
This article is cited in 1 scientific paper (total in 1 paper)
Finite automata and numbers
S. V. Aleshin, P. A. Panteleev Lomonosov Moscow State University
Abstract:
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.
Received: 03.07.2015
Citation:
S. V. Aleshin, P. A. Panteleev, “Finite automata and numbers”, Diskr. Mat., 27:4 (2015), 3–20; Discrete Math. Appl., 26:3 (2016), 131–144
Linking options:
https://www.mathnet.ru/eng/dm1343https://doi.org/10.4213/dm1343 https://www.mathnet.ru/eng/dm/v27/i4/p3
|
|