Automatic sequences (Q1856324)

The protoype for an automatic sequence is the Thue-Morse sequence \((t_n)_{n\geq0}\) defined recursively by \(t_0=0, t_{2n}=t_n, t_{2n+1}=1-t_n\). Each of the following properties characterises this sequence: - the 2-kernel which is the set of subsequences \((t_{2^kn+j})_{n\geq0}\) is finite - the 2-substitution \(0\to01,\) \(1\to10\) generates\((t_n)\) by starting the \(t_0=0\) and iterating the substitution - the sequence \((t_n)\) can be generated by a 2-automaton whose transition graph represents the substitution - the generating function \(T(x)=\sum_{n\geq0}t_nx^n\) satisfies a Mahler functional equation over \({\mathbb F}_2\), namely \[ T(x)=(1+x)T(x^2) +{x\over 1+x^2}=(1+x)T(x)^2+{x\over 1+x^2}. \] The binomial coefficients \(s_{nk}={n\choose k}\bmod 2\) provide an example of a double sequence with parallel properties: - the generating function over \({\mathbb F}_2\) is \[ P(x,y)=\sum_{n\geq0}(1+x)^ny^n=P(x^2,y^2)(1+y+xy)={1\over 1+y(1+x)} \] - the double sequence is generated by the (\(2\times2\))-substitution \(1\to\begin{matrix} 1 1\\ 1 0\end{matrix},\) \(0\to\begin{matrix} 0 0\\ 0 1 \end{matrix}\) - the (\(2\times2\))-kernel of the double sequence is finite - the double sequence is generated by a (\(2\times2\))-automaton - the double sequence is the orbit of a cellular automaton. The author develops a general approach to all this for sequences \(\Sigma(\Gamma,A)\) defined over a finitely generated group \(\Gamma\) with values in a finite set \(A\). There are analogues of substitutions \(S:\Sigma(\Gamma,A)\rightarrow \Sigma(\Gamma,A)\), finite automata and Mahler equations and, with certain additional considerations, the generalisations of the above properties of the Thue-Morse sequence are equivalent. The theory is rich and connects with logic, complexity theory and transcendental number theory. The book is only concerned with the general algebraic formalism, but includes examples and comments about these connected fields and a comprehensive bibliography on automatic sequences.