Automata finiteness criterion in terms of van der Put series of automata functions

Vladimir Anashin

In the paper we develop the $p$-adic theory of discrete automata. Every automaton $\mathfrak A$ (transducer) whose input/output alphabets consist of $p$ symbols can be associated to a continuous (in fact, 1-Lipschitz) map from $p$-adic integers to $p$ integers, the automaton function $f_\mathfrak A$. The $p$-adic theory (in particular, the $p$-adic ergodic theory) turned out to be very efficient in a study of properties of automata expressed via properties of automata functions. In the paper we prove a criterion for finiteness of the number of states of automaton in terms of van der Put series of the automaton function. The criterion displays connections between $p$-adic analysis and the theory of automata sequences.

Knowledge Graph



Sign up or login to leave a comment