Motivated by near-identical graphs of two increasing continuous functions—one related to Zaremba’s conjecture and the other due to Salem—we provide an explicit connection between fractals and regular sequences by showing that the graphs of ghost distributions, the distribution functions of measures associated to regular sequences, are sections of self-affine sets. Additionally, we provide a sufficient condition for such measures to be purely singular continuous. As a corollary, and analogous to Salem’s strictly increasing singular continuous function, we show that the ghost distributions of the Zaremba sequences are singular continuous.

The ring $\mathbb Z_{d}$ of d-adic integers has a natural interpretation as the boundary of a rooted d-ary tree $T_{d}$ . Endomorphisms of this tree (that is, solenoidal maps) are in one-to-one correspondence with 1-Lipschitz mappings from $\mathbb Z_{d}$ to itself. In the case when $d=p$ is prime, Anashin [‘Automata finiteness criterion in terms of van der Put series of automata functions’,p-Adic Numbers Ultrametric Anal. Appl. 4(2) (2012), 151–160] showed that $f\in \mathrm {Lip}^{1}(\mathbb Z_{p})$ is defined by a finite Mealy automaton if and only if the reduced coefficients of its van der Put series constitute a p-automatic sequence over a finite subset of $\mathbb Z_{p}\cap \mathbb Q$ . We generalize this result to arbitrary integers $d\geq 2$ and describe the explicit connection between the Moore automaton producing such a sequence and the Mealy automaton inducing the corresponding endomorphism of a rooted tree. We also produce two algorithms converting one automaton to the other and vice versa. As a demonstration, we apply our algorithms to the Thue–Morse sequence and to one of the generators of the lamplighter group acting on the binary rooted tree.

We show that spacetime diagrams of linear cellular automata $\unicode[STIX]{x1D6F7}:\,\mathbb{F}_{p}^{\mathbb{Z}}\rightarrow \mathbb{F}_{p}^{\mathbb{Z}}$ with $(-p)$-automatic initial conditions are automatic. This extends existing results on initial conditions that are eventually constant. Each automatic spacetime diagram defines a $(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D6F7})$-invariant subset of $\mathbb{F}_{p}^{\mathbb{Z}}$, where $\unicode[STIX]{x1D70E}$ is the left shift map, and if the initial condition is not eventually periodic, then this invariant set is nontrivial. For the Ledrappier cellular automaton we construct a family of nontrivial $(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D6F7})$-invariant measures on $\mathbb{F}_{3}^{\mathbb{Z}}$. Finally, given a linear cellular automaton $\unicode[STIX]{x1D6F7}$, we construct a nontrivial $(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D6F7})$-invariant measure on $\mathbb{F}_{p}^{\mathbb{Z}}$ for all but finitely many $p$.

We conjecture that bounded generalised polynomial functions cannot be generated by finite automata, except for the trivial case when they are ultimately periodic.

Using methods from ergodic theory, we are able to partially resolve this conjecture, proving that any hypothetical counterexample is periodic away from a very sparse and structured set. In particular, we show that for a polynomial $p(n)$ with at least one irrational coefficient (except for the constant one) and integer $m\geqslant 2$, the sequence $\lfloor p(n)\rfloor \hspace{0.2em}{\rm mod}\hspace{0.2em}m$ is never automatic.

We also prove that the conjecture is equivalent to the claim that the set of powers of an integer $k\geqslant 2$ is not given by a generalised polynomial.

Following up on a paper of Balamohan et al. [‘On the behavior of a variant of Hofstadter’s $q$-sequence’, J. Integer Seq. 10 (2007)], we analyze a variant of Hofstadter’s $Q$-sequence and show that its frequency sequence is 2-automatic. An automaton computing the sequence is explicitly given.

We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is strictly contained in that of k-regular sequences. Moreover, we show that equality of factors in a k-synchronized sequence is represented, in base k, by a right synchronized rational relation. This result allows us to prove that the separator sequence of a k-synchronized sequence is a k-synchronized sequence, too. This generalizes a previous result of Garel, concerning k-regularity of the separator sequences of sequences generated by iterating a uniform circular morphism.