Günter Rote:

Sequences with subword complexity 2n

Journal of Number Theory 46 (1993), 196-213, (Zbl 804.11023).


We discuss infinite 0-1-sequences which contain 2n different subwords of length n, for every n.

We give a method which can in principle construct all such sequences, using purely combinatorial tools. After giving some concrete examples of sequences with different properties, we give alternate methods for constructing special classes of sequences of complexity 2n.

The special class of sequences whose sets of subword are closed under complementation (exchanging 0's and 1's) is closely related to Sturmian sequences (sequences of complexity n+1), which are well understood.

Keywords: L-systems, infinite words, iterated morphisms

  PostScript file (gzippedpdf file  TeX .dvi file (figures not complete) (gzipped)