Decidability problems in infinite semigroups

Speaker(s)

Ruiwen Dong

Affiliation

Saarland University

Date

Nov. 29, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---