{"id":2533,"date":"2022-12-28T10:38:22","date_gmt":"2022-12-28T08:38:22","guid":{"rendered":"https:\/\/mathematics.haifa.ac.il\/?p=2533"},"modified":"2023-01-10T20:30:26","modified_gmt":"2023-01-10T18:30:26","slug":"colloquium-tuesday-january-3-2023-speaker-arseny-shur-ural-federal-university-title-words-separation-problem-and-short-identities-in-semigroups-and-groups","status":"publish","type":"post","link":"https:\/\/mathematics.haifa.ac.il\/?p=2533","title":{"rendered":"Colloquium: Tuesday January 3, 2023. Speaker: Arseny Shur (Ural Federal University). Title: “Words separation problem and short identities in semigroups and groups”."},"content":{"rendered":"\n

<\/p>\n\n\n\n

Our next Math colloquium talk will be in person<\/strong> next week on the 3rd of January, in room 614, Science & Education building.<\/p>\n\n\n\n

A zoom link for our meetings is:<\/p>\n\n\n\n

https:\/\/us02web.zoom.us\/j\/83337601824<\/a><\/p>\n\n\n\n

Speaker : Arseny Shur (Ural Federal University)<\/strong><\/p>\n\n\n\n

Date : Tuesday, 3rd of January, 2023.<\/strong><\/p>\n\n\n\n

Time : 14:00<\/strong><\/p>\n\n\n\n

Title: <\/strong>Words separation problem and short identities in semigroups and groups.<\/p>\n\n\n\n

Abstract: <\/strong>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 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, with no inverses, in the symmetric group on \"k\" elements.<\/p>\n","protected":false},"excerpt":{"rendered":"

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…
Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-2533","post","type-post","status-publish","format-standard","hentry","category-colloquium"],"_links":{"self":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2533"}],"version-history":[{"count":2,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2533\/revisions"}],"predecessor-version":[{"id":2544,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2533\/revisions\/2544"}],"wp:attachment":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}