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

Abstract

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-adic 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.

Identifiers

DOI

10.1134/s2070046612020070

Citations and references