Theory Talk by Juhani Karhumaki, University of Turku, Finland

Speaker:  Juhani Karhumaki, Professor, University of Turku

Title:  Combinatorics on Words and k-Abelian Equivalence

Hosts:  Jano Manuch & David Kirkpatrick

Abstract:

We define a new equivalence relation on words which is properly in between the equality and commutative (abelian) equality. We call it k-abelian  equality.  We say that two words are  k-abelian equal if they contain each factor of length k equally many times, and in addition start with a common prefix of length  k-1. This allows to have better and better approximations of problems based on equality of words. We report basic properties of these equivalence relations, and analyze k-abelian variants of some well known problems on words. In particular we consider problems dealing local and global regularities in infinite words, as well as the existence of certain type of repetition-free words. It turns out that there exists a lot of challenging open problems in this area.

Bio:

Juhani Karhumaki obtained his PhD from University of Turku, Finland in 1976. In 1980 he became an associate professor (docent) in Department of Mathematics at University of Turku, in 1989 an acting professor and in 1998 a full professor at the same department. During his early academic years, he was a junior researcher of Finnish Academy of Sciences (1980-85) and a visiting associate professor at University of Waterloo and University South Carolina. He is a member of Finnish Academy of Sciences since 2000, a member of Academia Europaea since 2006 and currently the director of FUNDIM Centre (Fundamentals of Computing and Discrete Mathematics; www.math.utu.fi/fundim/). Juhani's research is focused on automata theory, combinatorics of words and decidability questions. For more information visit his website at https://www.utu.fi/en/university/faculty-of-science-and-engineering/units.