Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


Decidability problems in infinite semigroups

Prelegent: Ruiwen Dong

2023-11-29 14:15

This talk is about several algorithmic problems for matrix semigroups. A classic problem in this area is the well-known Semigroup Membership problem: given as input a finite set of square matrices S = {A1, A2, ... Ak} and a matrix A, decide whether there exists a sequence of matrices from S whose product is equal to A. This problem is highly intractable and has been shown to be undecidable even for integer matrices of dimension four. For this reason, we focus on the special case where the matrix A is restricted the identity matrix. This is called the Identity Problem, and enjoys the property of being decidable for a much larger class of matrices, while remaining undecidable for general matrices. We aim towards a group-theoretic classification of the cases where the Identity Problem is decidable.