Günter Rote:

Sequences with subword complexity 2n

Abstract

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

Errata

1. I thank Jeff Shallit for pointing out the following mistake in connection with Theorem 2. The theorem holds as stated, but contrary to what is claimed in the beginning of the proof (p. 204) and mentioned in the remark after the proof (p. 205), the condition θ<min(φ, 1−φ) is not necessary.

   The necessity argument is valid for θ<1/2. However, it is clear that θ and 1−θ generate essentially the same orbit on the unit circle, except that the points rotate in the opposite direction. Thus, when θ>1/2 (which is excluded under the current assumptions), the theorem should be applied with θ replaced by 1−θ.

   Another way to say this is that the condition θ<min(φ, 1−φ) (and θ>0), which is equivalent to θ<φ<1−θ (and θ>0), should be replaced by

   0 < min(θ, 1−θ) < φ < max(θ, 1−θ).

2. The algorithm on p. 198 is not properly aligned: The for-loop extends over the whole algorithm until end for, and it includes the three if-statements.
3. In the last sentence of Section 2 (p. 203), read repentantly (instead of repentently*).

Last update: June 21, 2024.