Automatic Logarithm and Associated Measures Academic Article uri icon

abstract

  • We introduce the notion of the Automatic Logarithm $mathcal L_{mathcal A, mathcal B}$ with the purpose of studying the expanding properties of Schreier graphs of action of the group generated by two finite initial Mealy automata $mathcal A$ and $mathcal B$ on the levels of a regular $d$-ary rooted tree $mathcal T$, where $mathcal A$ is level-transitive and of bounded activity. $mathcal L_{mathcal A, mathcal B}$ computes the lengths of chords in this family of graphs. Formally, $mathcal L$ is a map $partial mathcal T
    ightarrow mathbb{Z}_d$ from the boundary of the tree to the integer $p$-adics whose values are determined by a Moore machine. The distribution of its outputs 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 illustrating the different cases with $mathcal A$ being the adding machine is provided.

author list (cited authors)

  • Grigorchuk, R., Kogan, R., & Vorobets, Y.

complete list of authors

  • Grigorchuk, Rostislav||Kogan, Roman||Vorobets, Yaroslav

publication date

  • November 2018