The meeting #219 will be held on June 1 at 18:00 (Omsk time), 19:00 (Novosibirsk time), 07:00 (New York time), 15:00 (Moscow time).
Alexander Rybalov (Sobolev Institute of Mathematics SB RAS) will present his talk
"Generic complexity of two problems about semigroups".
First problem is the word problem for some finitely defined semigroups. In 2008 Won suggested a simple generic algorithm for the word problem in finitely defined semigroups. It works for classical semigroups with undecidable word problem: Tseitin semigroup, Makanin semigroup. But it does not work for semigroups with one relation. The problem of existence of algorithms for word problem in these semigroups is still open, despite the efforts of Adjan and his students. In this talk I present a polynomial generic algorithm for some finitely defined semigroups, which works for Tseitin semigroups and semigroups with one relation.
Second problem is the isomorphism problem for finite semigroups, represented by multiplication tables. Kornienko, Zinchenko and Tyshkevich in 1982 proved that the famous graph isomorphism problem can be reduced in polynomial time to the isomorphism problem for finite semigroups. Thus it is still unknown, does it decidable in polynomial time. In this talk I will present a polynomial generic algorithm for the isomorphism problem for finite semigroups.
You can connect to the Zoom conference via this link: or manually in the Zoom app using the conference ID 812 2079 3393.
Please pay attention to the following rules for conducting an Internet seminar:
- Please, use your real first and last name
- Keep your microphone off during the talk
- Should you have any questions, ask them in the chat
