Automatic walks (Q1311045): Difference between revisions

Let \(f: A\to G\) be a map from a set \(A\) to a locally compact abelian group \(G\). A sequence \(x= (x_ n)_ n\) determines a walk \((S_ n(x))_ n\) on \(G\) through \(S_ 0(x)=e\) and \(S_ n(x)= f(x_ 1)+ \cdots+ f(x_ n)\). The case \(A=\mathbb{R}\), \(G=\mathbb{C}\), \(f(x)= e^{2\pi ix}\) corresponds to the classical walks associated with exponential sums. The author discusses results for automatic sequences \(x\), that is sequences recognizable by finite automata, concentrating on the classification of the walks as recurrent \((\| S_ n(x)\| <\varepsilon)\), ultimately recurrent, transient (that is, not ultimately recurrent), or bounded. The notion can be extended to a walk on a graph. Some interesting results for the case in which \(A\) has cardinality 2 are discussed.