[Colloq] TALK: Tuesday, April 14, 11 AM: k-Abelian Complexity: A New Complexity Measure for Infinite Words

[Rajmohan Rajaraman]

TITLE: k-Abelian Complexity: A New Complexity Measure for Infinite Words

SPEAKER: Juhani Karhumäki
         Department of Mathematics and Statistics
         University of Turku, Finland

WHEN: Tuesday, April 14, 11 AM

WHERE: 366 WVH

ABSTRACT:

k-abelian equivalence of words was recently introduced as an equivalence relation in-
between the equality and abelian equality of words. It identifies words which have
equally many occurrences of all words of length k (and, as a technicality, share a prefix of length k-1). 
For finite words this provides an infinite sequence approximating the equality of words.

One way of defining the complexity of infinite words is to count unequal factors of
different lengths. k-abelian complexity states a natural measure of this type. This is
the topic of this talk. Bounds for these complexities are given by the numbers of the
equivalence classes for different values of k and the cardinality of the alphabet. The
upper bounds are known to be polynomial, however, the degrees of these polynomials
grow exponentially in k.

We concentrate on the following two questions: (i) How much the complexity can grow when we move from level
k - 1 to level k; (ii) How much the k-abelian complexity can 
fluctuate, i.e., how much the growth rates of the "minimal" and "maximal" values of the complexity can deviate?

Our results give more or less exhaustive answers to these questions. In the first
problem the jump can be from a constant to Theta(Max_k(n)/Max_{k-1}(n)); where Max_k(n)
denotes the maximal k-abelian complexity. The answer to the question (ii) is more
subtle. The fluctuation cannot be maximal, but indeed can be close to that. Namely,
we construct examples where the fluctuation is from Theta(1) to o(Max_k(n)), as well as
from Theta(n) to Theta(Max_k(n)). On the other hand, the fuctuation all the way from o(n) to Theta(Max_k(n)) is not possible.

(in collaboration with J. Cassaigne, A. Saarela and L. Zamboni)

BIO:

Juhani Karhumäki graduated at the University of Turku in mathematics in 1973, and completed his Ph.D. in the same university under the supervision of Academician Arto Salomaa in 1976. J. Karhumäki has had a number of long (up to one year) and short (one month) visitor’s positions e.g. in the University of Waterloo, Ontario, in the University of Southern Carolina (Columbia), and in several universities in France, e.g. the University of Diderot in Paris. His main research topics are automata theory and especially recently, combinatorics on words. He has been a full professor in discrete mathematics at the University of Turku since 1989, and a chair professor and head of the department of mathematics since 1998. J. Karhumäki has been a frequent PC member at most of the main conferences of theoretical computer science in Europe, and one of the most frequent speakers in ICALP conferences. He is also a member of Finnish Academy of Sciences and Letters and Academia Europaea. 

Best,

Rajmohan.