
Subword Complexity of Infinite Words
J. Cassaigne Institut de Mathematiques de Luminy, Marseille France 

Abstract 1:
The Kolakoski sequence and its conjectured subword
complexity
The
Kolakoski sequence is the sequence K with values in {1,2}
such that K(n) is equal to the length of the nth run of equal
symbols in K. This is an intriguing sequence, for which apparently
simple questions turn out to be very difficult problems. Dekking conjectured in
1981 that its subword complexity function
p_{K}(n)
was equivalent to Cn^{p} with p=log3/log(3/2). We prove,
under the hypothesis that the set of subwords of K is invariant under the
exchange of 1 and 2, the inequality
p_{K}(n)
>= Cn^{p}, and, under the additional hypothesis that 1 and
2 occur with the same frequency (which is a famous open problem), that
p_{K}(n)
=O(n ^{p+e}) for any
positive e.
Information:
Date:  August 3, 2005, 10:0011:00 
Place:  School of Mathematics, Niavaran Bldg., Niavaran Square, Tehran, Iran 

Abstract 2:
Special factors of sequences with linear subword complexity
Sequences with low
complexity, which means that p(n) does not grow too fast (e.g., it is
bounded by a linear function), are certainly the sequences with the most
interesting features, as this constraint on complexity induces certain
regularities in the sequence, without however making it periodic. Their
properties have been extensively studied; among them is the famous class of
Sturmian sequences for which the complexity is as low as possible for
nonperiodic sequences:
p(n)=n+1.
No characterization of the set of integervalued functions that can arise as
subword complexities of sequences is known; nevertheless it is clear that not
all functions are obtainable this way. For instance, complexity functions are
necessarily monotonically increasing, and they can neither grow faster than k^{n}
nor more slowly than n, except when they are stationary. In this talk we
establish a subtler restriction, which was conjectured by S. Ferenczi: if
p(n) has linear growth (i.e., p(n) is bounded by some linear
function), then its differences p(n+1)p(n) are bounded.
The proof of this result uses a combination of two combinatorial representations
of the set of factors of a sequence: Rauzy graphs and special
factor trees. A crucial notion for this proof (and for many related
problems) is that of right (and left) special factors, i.e.,
factors that can be extended in more than one way to longer factors by adding
one letter to the right (or left).
When the alphabet has only two letters, the number of right special factors is
exactly the quantity p(n+1)p(n) we are interested in.
Information:
Date:  August 3, 2005, 14:0015:00 
Place:  School of Mathematics, Niavaran Bldg., Niavaran Square, Tehran, Iran 

 
