Automatic sequences

MaRDI QIDQ1856324zbMATH OpenFDO

Authors Fritz von Haeseler

Publication date 2 February 2003

Published in De Gruyter Expositions in Mathematics (Search for Journal in Brave)

zbMATH Keywords

automatic sequences substitutions

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to number theory (11-02) Automata sequences (11B85) Algebraic theory of languages and automata (68Q70) Cellular automata (computational aspects) (68Q80) Combinatorics on words (68R15)

Review text

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.

Recommendations

Cited in

(53)

This page was built for publication: Automatic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1856324)