Automatic complexity of shift register sequences

Let x be an m-sequence, a maximal length sequence produced by a linear feedback shift register. We show that x has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity AN(x) is close to maximal: n∕2−AN(x)=O(log2n), where n is the length of x. In contrast, Hyde has shown AN(y)≤n∕2+1 for all sequences y of length n.