Automatic logarithm and associated measures

Abstract

We introduce the notion of the automatic logarithm \(\operatorname{Log}_{\mathcal A}(\mathcal B)\) of a finite initial Mealy automaton \(\mathcal B\), with another automaton \(\mathcal A\) as the base. It allows one to find for any input word \(w\) a power \(n\) such that \(\mathcal B(w)=\mathcal A^n(w)\). The purpose is to study the expanding properties of graphs describing the action of the group generated by \(\mathcal A\) and \(\mathcal B\) on input words of a fixed length interpreted as levels of a regular \(d\)-ary rooted tree \(\mathcal T\). Formally, the automatic logarithm is a single map \(\operatorname{Log}_{\mathcal A}(\mathcal B)\colon\partial \mathcal T \rightarrow \mathbb{Z}_d\) from the boundary of the tree to the \(d\)-adic integers. Under the assumption that the action of the automaton \(\mathcal A\) on the tree \(\mathcal T\) is level-transitive and of bounded activity, we show that \(\operatorname{Log}_{\mathcal A}(\mathcal B)\) can be computed by a Moore machine. The distribution of values of the automatic logarithm yields a probabilistic measure \(\mu\) on \(\partial \mathcal T\), which in some cases can be computed by a Mealy-type machine (we then say that \(\mu\) is finite-state). We provide a criterion to determine whether \(\mu\) is finite-state. A number of examples with \(\mathcal A\) being the adding machine are considered.