Laboratory of Mathematical Logic at PDMI

Пятница, 19 октября, ауд. 203. Начало в 18:00.

Докладчик: Juhani Karhumäki (University of Turku).

Тема: K-abelian equivalence of words.

Abstract

We talk about recently studied notion of k-Abelian equivalence of words over a fixed finite alphabet. It is a congruence defined as follows. For a fixed natural number k two words are k-abelian equivalent if they have, for each word of lenght at most k, an equal number of occurrence of factors of this word, and moreover, they have common prefixis (and suffixis) of lenght k-1. Clearly the relation is in between equality and abelian equality of words; in fact, it defines an infinite hierarchy of approximations of equality when kgoes to infinity.

We talk about the basic properties of this notion, and in additon, analyze it in different problems of automata theory and combinatorics on words. In particular, we consider variants of classical problems,like Post Correspondence Problem in this setting. We also analyze some questions on unavoidabllity regulariies connected to these notions and relate those to the similar problems on words and abelian words. Moreover, we look at several natural unavoidability questions on infinite words.

Besides results mentioned in this talk our main motivation is to propose problems related to this interesting equivalence relation, and in particular, to point out that there are not only many but also several very challenging problems to be studied in this framework.