Colloquium: Tuesday January 3, 2023. Speaker: Arseny Shur (Ural Federal University). Title: “Words separation problem and short identities in semigroups and groups”.

Author: raphy December 28, 2022

Our next Math colloquium talk will be in person next week on the 3rd of January, in room 614, Science & Education building.

A zoom link for our meetings is:

https://us02web.zoom.us/j/83337601824

Speaker : Arseny Shur (Ural Federal University)

Date : Tuesday, 3rd of January, 2023.

Time : 14:00

Title: Words separation problem and short identities in semigroups and groups.

Abstract: Consider a very simple algorithmic problem: given two distinct words $u$ and $v$ in advance, decide whether the input word is $u$ or $v$ . Suppose that the decision procedure should also be simple: acceptance/rejection by a deterministic finite automaton. We say that the automaton separates $u$ and $v$ if it accepts exactly one of them. What is the minimum size $sep(u,v)$ of a DFA separating $u$ and $v$ ? What is the mnimum size $k = sep(n)$ such that any two words of length at most $n$ are separated by an automaton with at most $k$ states? We will focus on the exact values (for small $n$ ) and the asymptotics of the function $sep(n)$ . This problem can be easily reformulated as finding the minimum length of an identity of the full transformation semigroup on $k$ elements. Most of the time we will speak about important particular case where the DFA must be invertible, that is, each letter must act as a permutation of the set of states. This case corresponds to finding short identities of the form $u = v$ , with no inverses, in the symmetric group on $k$ elements.