Automatic logarithm and associated measures

• Datum: 2023
• Hauptverfasser: Grigorchuk, R., Kogan, R., Vorobets, Y.
• Format: Artikel
• Sprache: English
• Veröffentlicht: Lugansk National Taras Shevchenko University 2023
• Schlagworte: Mealy automaton; Moore machine; regular rooted tree; Markov measure; finite-state measure; 20E08; 37B10; 60B05; 68Q45
• Online Zugang: https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2014
• Назва журналу: Algebra and Discrete Mathematics

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.