##
Günter Rote:

#
Sequences with subword complexity 2*n*

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

We discuss infinite 0-1-sequences which contain 2*n* 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 2*n*.

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