Colloquium: Tuesday January 3, 2023. Speaker: Arseny Shur (Ural Federal University). Title: “Words separation problem and short identities in semigroups and groups”.
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 and
in advance, decide whether the input word is
or
. Suppose that the decision procedure should also be simple: acceptance/rejection by a deterministic finite automaton. We say that the automaton separates
and
if it accepts exactly one of them. What is the minimum size
of a DFA separating
and
? What is the mnimum size
such that any two words of length at most
are separated by an automaton with at most
states? We will focus on the exact values (for small
) and the asymptotics of the function
. This problem can be easily reformulated as finding the minimum length of an identity of the full transformation semigroup on
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
, with no inverses, in the symmetric group on
elements.