Понедельник, 21 декабря, ауд. 402(?). Начало в 16:00.
Докладчик: Juhani Karhumäki (University of Turku).
Тема: ON COMPLEXITY OF K-ABELIAN CLASSES.
Abstract
K-abelian equivalence gives an approximation of the equality of words. It is defined by counting the numbers of occurrences of factors of legth k in a word. It is an equivalence relation, in fact, a congruence. We consider two complexity issues of these equivalence classes: their number and there size of words of length n. Crucial observation is the characterization of these classes in terms of rewriting. This allows to find canonical representations of the clases. This turns out to be a rational language, thus showing that the complexity funcion is rational for all values of k in any alhabet. More precisely this allows to detrmine its exact value, in theory. In practice the automata are unmanageble even for relatively small values of the parameters.
We also consider singleton equivalence classes, and notice the evaluation of their number is connected to an old problem on necklaces.
