Finite automata and numbers
Станислав Владимирович Алешин, Pavel Panteleev · Discrete Mathematics and Applications · 2016
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.