Günter Rote:
Sequences with subword complexity 2n
Journal of Number Theory 46 (1993), 196–213,
(Zbl 804.11023).
doi:10.1006/jnth.1994.1012 →BibTeX
Abstract
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
Errata
-
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−θ).
- 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.
- In the last sentence of Section 2 (p. 203),
read repentantly
(instead of *repentently).
Last update: July 16, 2024.