How to prove that a sequence is not automatic (Q2121041): Difference between revisions

Introduced by Cobham, automatic sequences are widely used in combinatorics on words and related fields. They are the images under a coding of the fixed point of a morphism (or substitution) of constant length. The purpose of this survey paper is to give a manual for proving that a given sequence is not automatic. The discussed techniques make use of infinite kernels, irrational frequencies, block (or factor, subword) complexity, gaps and runs, orbits or eigenvalues of a dynamical system. Many examples and useful pointers to the literature are also provided. In particular, when the sequences take their values in a finite field \(\mathbb{F}_q\), this also permits proving that the associated formal power series are transcendental over \(\mathbb{F}_q (X )\). This paper is of clear interest to anyone encountering a new sequence for which properties are to be discovered.