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.
Fulltext:
PDF file (668 kB)