Decidability problems in infinite semigroups

Prelegent(ci)

Ruiwen Dong

Afiliacja

Saarland University

Termin

29 listopada 2023 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---